{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Color Value in a Directed Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #topological-sort #memoization #hash-table #dynamic-programming #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #拓扑排序 #记忆化搜索 #哈希表 #动态规划 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestPathValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有向图中最大颜色值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>有向图</strong> ，它含有 <code>n</code> 个节点和 <code>m</code> 条边。节点编号从 <code>0</code> 到 <code>n - 1</code> 。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>colors</code> ，其中 <code>colors[i]</code> 是小写英文字母，表示图中第 <code>i</code> 个节点的 <b>颜色</b> （下标从 <strong>0</strong> 开始）。同时给你一个二维数组 <code>edges</code> ，其中 <code>edges[j] = [a<sub>j</sub>, b<sub>j</sub>]</code> 表示从节点 <code>a<sub>j</sub></code> 到节点 <code>b<sub>j</sub></code><sub> </sub>有一条 <strong>有向边</strong> 。</p>\n",
    "\n",
    "<p>图中一条有效 <strong>路径</strong> 是一个点序列 <code>x<sub>1</sub> -&gt; x<sub>2</sub> -&gt; x<sub>3</sub> -&gt; ... -&gt; x<sub>k</sub></code> ，对于所有 <code>1 &lt;= i &lt; k</code> ，从 <code>x<sub>i</sub></code> 到 <code>x<sub>i+1</sub></code> 在图中有一条有向边。路径的 <strong>颜色值</strong> 是路径中 <strong>出现次数最多</strong> 颜色的节点数目。</p>\n",
    "\n",
    "<p>请你返回给定图中有效路径里面的 <strong>最大颜色值</strong><strong> 。</strong>如果图中含有环，请返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/21/leet1.png\" style=\"width: 400px; height: 182px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>colors = \"abaca\", edges = [[0,1],[0,2],[2,3],[3,4]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>路径 0 -&gt; 2 -&gt; 3 -&gt; 4 含有 3 个颜色为 <code>\"a\" 的节点（上图中的红色节点）。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/21/leet2.png\" style=\"width: 85px; height: 85px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>colors = \"a\", edges = [[0,0]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>从 0 到 0 有一个环。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == colors.length</code></li>\n",
    "\t<li><code>m == edges.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= m &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>colors</code> 只含有小写英文字母。</li>\n",
    "\t<li><code>0 &lt;= a<sub>j</sub>, b<sub>j</sub> &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-color-value-in-a-directed-graph](https://leetcode.cn/problems/largest-color-value-in-a-directed-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-color-value-in-a-directed-graph](https://leetcode.cn/problems/largest-color-value-in-a-directed-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abaca\"\\n[[0,1],[0,2],[2,3],[3,4]]', '\"a\"\\n[[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        adj = [[] for _ in range(len(colors))]\n",
    "        indeg = [0 for _ in range(len(colors))]\n",
    "        for e in edges:\n",
    "            indeg[e[1]] += 1\n",
    "            adj[e[0]].append(e[1])\n",
    "        max_path = 0\n",
    "        for c in range(26):\n",
    "            result = self.bfs(chr(c+ord('a')), adj, indeg[:], colors)\n",
    "            if result == -1: return -1\n",
    "            max_path = max(max_path, result)\n",
    "        return max_path\n",
    "    \n",
    "    def bfs(self, color, adj, indeg, colors):\n",
    "        q = deque()\n",
    "        for i in range(len(colors)):\n",
    "            if indeg[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        out_num = 0\n",
    "        color_count = [1 if colors[i] == color else 0 for i in range(len(colors))]\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            out_num += 1\n",
    "\n",
    "            for v in adj[u]:\n",
    "                indeg[v] -= 1\n",
    "                # pass on color value\n",
    "                temp = color_count[u] + 1 if colors[v] == color else color_count[u]\n",
    "                color_count[v] = max(color_count[v], temp)\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "        if out_num != len(colors):\n",
    "            return -1\n",
    "        return max(color_count)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = defaultdict(list)\n",
    "        in_degs_orig = [0 for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            in_degs_orig[v] += 1\n",
    "        q_orig = deque([i for i in range(n) if in_degs_orig[i] == 0])\n",
    "        ans = 0\n",
    "        for c in range(26):\n",
    "            color = chr(c + ord(\"a\"))\n",
    "            in_degs = copy.copy(in_degs_orig)\n",
    "            q = copy.copy(q_orig)\n",
    "            f = [0 for _ in range(n)]\n",
    "            for u in q:\n",
    "                if colors[u] == color:\n",
    "                    f[u] = 1\n",
    "            vis = 0\n",
    "            while q:\n",
    "                m = len(q)\n",
    "                for i in range(m):\n",
    "                    u = q.popleft()\n",
    "                    vis += 1\n",
    "                    for v in g[u]:\n",
    "                        f[v] = max(f[v], f[u] + (colors[v] == color))\n",
    "                        in_degs[v] -= 1\n",
    "                        if in_degs[v] == 0:\n",
    "                            q.append(v)\n",
    "            if vis < n:\n",
    "                return -1\n",
    "            ans = max(ans, max(f))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        color_set = set(colors)\n",
    "        m,n,vis = len(color_set),len(colors),0\n",
    "        mapping = dict(zip(color_set,range(m)))\n",
    "        colors = list(map(lambda c:mapping[c],colors))\n",
    "        s = [[0]*m for _ in range(n)]\n",
    "        g,d = [[] for _ in range(n)],[0]*n\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            d[b] += 1\n",
    "        q = list(filter(lambda i:d[i]==0,range(n)))\n",
    "        for x in q: s[x][colors[x]] = 1\n",
    "        while q:\n",
    "            x = q.pop()\n",
    "            vis += 1\n",
    "            for y in g[x]:\n",
    "                d[y] -= 1\n",
    "                for c in range(m): s[y][c] = max(s[y][c],s[x][c] + (c == colors[y]))\n",
    "                if d[y] == 0: q.append(y)\n",
    "        return max(map(max,s)) if vis == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        indegree = {i : 0 for i in range(n)}\n",
    "        u2v = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            indegree[v] += 1\n",
    "            u2v[u].append(v)\n",
    "        q = [i for i in range(n) if indegree[i] == 0]\n",
    "        tp = []\n",
    "        while q:\n",
    "            u = q.pop(0)\n",
    "            tp.append(u)\n",
    "            for v in u2v[u]:\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    q.append(v)\n",
    "        if len(tp) != n:\n",
    "            return -1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(26):\n",
    "            c = chr(i + ord('a'))\n",
    "            dp = [0] * n\n",
    "            for idx in range(n - 1, -1, -1):\n",
    "                for v in u2v[tp[idx]]:\n",
    "                    dp[tp[idx]] = max(dp[tp[idx]], dp[v])\n",
    "                if colors[tp[idx]] == c:\n",
    "                    dp[tp[idx]] += 1\n",
    "            ans = max(ans, max(dp))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = [[] for _ in range(n)]\n",
    "        ind = [0] * n\n",
    "        for u,v in edges:\n",
    "            if u == v:\n",
    "                return -1\n",
    "            ind[v] += 1\n",
    "            g[u].append(v)\n",
    "        \n",
    "        def chk(c, ind):\n",
    "            d = deque()\n",
    "            for i in range(n):\n",
    "                if ind[i] == 0:\n",
    "                    d.append(i)\n",
    "            if not d:\n",
    "                return -1\n",
    "            ret = 0\n",
    "            vis = set()\n",
    "            k = defaultdict(int)\n",
    "            while d:\n",
    "                t = d.popleft()\n",
    "                if colors[t] == c:\n",
    "                    k[t] += 1\n",
    "                ret = max(ret, k[t])\n",
    "                vis.add(t)\n",
    "                for i in g[t]:\n",
    "                    ind[i] -= 1\n",
    "                    k[i] = max(k[i], k[t])\n",
    "                    if ind[i] == 0:\n",
    "                        d.append(i)\n",
    "            if len(vis) != n:\n",
    "                return -1\n",
    "            return ret\n",
    "        r = 0\n",
    "        for i in range(26):\n",
    "            v = chk(chr(97+i), ind.copy())\n",
    "            if v == -1:\n",
    "                return -1\n",
    "            r = max(r, v)\n",
    "        return r\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        # 只有小写字母\n",
    "        \n",
    "        graph=defaultdict(list)\n",
    "        indegree=defaultdict(int)\n",
    "        for s,e in edges:\n",
    "            graph[s].append(e)\n",
    "            indegree[e]+=1\n",
    "        n=len(colors)\n",
    "        tmp=indegree.copy()\n",
    "        q=deque()\n",
    "        c=0\n",
    "        for i in range(n):\n",
    "            if tmp[i]==0:\n",
    "                q.append(i)\n",
    "                c+=1\n",
    "        \n",
    "        while q:\n",
    "            cnt=q.popleft()\n",
    "            for nxt in graph[cnt]:\n",
    "                tmp[nxt]-=1\n",
    "                if tmp[nxt]==0:\n",
    "                    q.append(nxt)\n",
    "                    c+=1\n",
    "        if c!=n:return -1\n",
    "\n",
    "\n",
    "        def get(x):\n",
    "            tmp=indegree.copy()\n",
    "            q=deque()\n",
    "            c=0\n",
    "            f=[0]*n\n",
    "            for i in range(n):\n",
    "                if tmp[i]==0:\n",
    "                    q.append(i)\n",
    "                    if colors[i]==x:f[i]=1\n",
    "            while q:\n",
    "                cnt=q.popleft()\n",
    "                for nxt in graph[cnt]:\n",
    "                    tmp[nxt]-=1\n",
    "                    if tmp[nxt]==0:\n",
    "                        q.append(nxt)\n",
    "                    f[nxt]=max(f[nxt],f[cnt]+int(colors[nxt]==x))\n",
    "            return max(f)\n",
    "        return max(get(i) for i in string.ascii_lowercase)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = [[] for _ in range(n)]\n",
    "        f = [[0]*n for _ in range(26)]\n",
    "        times = 0\n",
    "        ind = [0] * n\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            ind[y] += 1\n",
    "        q = deque([i for i in range(n) if not ind[i]])\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            times += 1\n",
    "            c = ord(colors[x]) - ord('a')\n",
    "            f[c][x] += 1\n",
    "            for y in g[x]:\n",
    "                ind[y] -= 1\n",
    "                if not ind[y]:q.append(y)\n",
    "                for i in range(26):\n",
    "                    f[i][y] = max(f[i][y],f[i][x])\n",
    "        if times != n: return -1\n",
    "        return max(max(row) for row in f)\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        uni_colors = set(colors)\n",
    "        m = len(uni_colors) # 一共有m种不同颜色\n",
    "        sequences = {x: i for i, x in enumerate(sorted(uni_colors))} # 每种颜色按升序排列后对应的序号\n",
    "        colors = [sequences[x] for x in colors] # 将每个节点对应的颜色转为序号\n",
    "        # 统计每个节点的入度和指向的节点，进行拓扑排序\n",
    "        in_degrees = [0] * n\n",
    "        out_degrees = [set() for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            in_degrees[j] += 1\n",
    "            out_degrees[i].add(j)\n",
    "        q = deque()\n",
    "        search_order = []\n",
    "        # node_colors[node][color]表示到达节点node的所有有效路径中，颜色color出现的最多次数\n",
    "        node_colors = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if not in_degrees[i]:\n",
    "                q.append(i)\n",
    "                node_colors[i][colors[i]] = 1\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            search_order.append(cur)\n",
    "            for nxt in out_degrees[cur]:\n",
    "                in_degrees[nxt] -= 1\n",
    "                if not in_degrees[nxt]:\n",
    "                    q.append(nxt)\n",
    "        # 如果拓扑排序结果小于n，说明存在环，返回-1\n",
    "        if len(search_order) < n:\n",
    "            return -1\n",
    "        ans = 1\n",
    "        # 广度优先搜索，计算出到达每个节点的所有有效途径，能获得的每个颜色的最大出现次数\n",
    "        for cur in search_order:\n",
    "            for nxt in out_degrees[cur]:\n",
    "                for color in range(m):\n",
    "                    node_colors[nxt][color] = max(node_colors[nxt][color],\n",
    "                                                  node_colors[cur][color] + (colors[nxt] == color))\n",
    "                    ans = max(ans, node_colors[nxt][color])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        graph = [[] for i in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i in range(len(edges)):\n",
    "            graph[edges[i][0]].append(edges[i][1])\n",
    "            degree[edges[i][1]] += 1\n",
    "\n",
    "        queue = []\n",
    "        createD = dict(zip(set(colors), [0] * len(set(colors))))\n",
    "        colorP = [copy.deepcopy(createD) for i in range(n)]\n",
    "        result = 1\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                queue.append(i)\n",
    "                colorP[i][colors[i]] += 1\n",
    "        while len(queue) != 0:\n",
    "            beginP = queue.pop(0)\n",
    "            if len(graph[beginP]) == 0:\n",
    "                result = max(result, max(colorP[beginP].values()))\n",
    "            for each in graph[beginP]:\n",
    "                degree[each] -= 1\n",
    "                for key in colorP[beginP].keys():\n",
    "                    if key == colors[each]:\n",
    "                        tmp = colorP[beginP][key] + 1\n",
    "                    else:\n",
    "                        tmp = colorP[beginP][key]\n",
    "                    colorP[each][key] = max(colorP[each][key], tmp)\n",
    "                if degree[each] == 0:\n",
    "                    queue.append(each)\n",
    "        \n",
    "        if sum(degree) != 0:\n",
    "            return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        #解题思路：\n",
    "        #动态规划，我们可以枚举颜色c，随后选出可以使得path_c最大的路径\n",
    "        #注意：如果给定的有向图包含环，那么它不存在拓扑排序。\n",
    "\n",
    "        n = len(colors)\n",
    "        indeg = [0] * n\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            indeg[b] += 1\n",
    "            graph[a].append(b)\n",
    "        q = [i for i,d in enumerate(indeg) if d == 0]\n",
    "        dp = [[0] * 26 for _ in range(n)]\n",
    "        res = 0\n",
    "        # 记录拓扑排序过程中遇到的节点个数，如果最终 found 的值不为 n，说明图中存在环\n",
    "        found = 0\n",
    "\n",
    "        while q:\n",
    "            found += 1\n",
    "            cur = q.pop(0)\n",
    "            dp[cur][ord(colors[cur]) - ord('a')] += 1\n",
    "            for child in graph[cur]:\n",
    "                indeg[child] -= 1\n",
    "                if indeg[child] == 0:\n",
    "                    q.append(child)\n",
    "                for c in range(26):\n",
    "                    dp[child][c] = max(dp[child][c],dp[cur][c])\n",
    "\n",
    "        if found != n:\n",
    "            return -1\n",
    "\n",
    "        for i in range(n):\n",
    "            res = max(res,max(dp[i]))\n",
    "        return res \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = [[] * n for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        f = [[0] * 27 for _ in range(n)]\n",
    "        for i in edges:\n",
    "            g[i[0]].append(i[1])\n",
    "            indegree[i[1]] += 1\n",
    "            if i[0] == i[1]:\n",
    "                return -1\n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                queue.append(i)\n",
    "        ans = 1\n",
    "        found = 0\n",
    "        while queue:\n",
    "            found += 1\n",
    "            cur = queue.pop(0)\n",
    "            f[cur][ord(colors[cur]) - ord('a')] += 1\n",
    "            for v in g[cur]:\n",
    "                indegree[v] -= 1\n",
    "                for c in range(27):\n",
    "                    f[v][c] = max(f[v][c], f[cur][c])\n",
    "                if indegree[v] == 0:\n",
    "                    queue.append(v)\n",
    "        if found != n:\n",
    "            return -1\n",
    "        for i in range(n):\n",
    "            ans = max(ans, max(f[i]))\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        # 拓扑排序的同时，动态规划。f[i][j]表示以i节点为结尾的路径中，j颜色节点的最大值\n",
    "        n = len(colors)\n",
    "        g = collections.defaultdict(list)\n",
    "        indeg = [0]*n\n",
    "\n",
    "        for x,y in edges:\n",
    "            indeg[y] += 1\n",
    "            g[x].append(y)\n",
    "        \n",
    "        found = 0\n",
    "        f = [[0]*26 for _ in range(n)]\n",
    "        \n",
    "        q = collections.deque([i for i in range(n) if indeg[i]==0])\n",
    "        while q:\n",
    "            found += 1\n",
    "            x = q.popleft()\n",
    "            f[x][ord(colors[x])-ord('a')] += 1\n",
    "\n",
    "            for y in g[x]:\n",
    "                indeg[y] -= 1\n",
    "                for c in range(26):\n",
    "                    f[y][c] = max(f[y][c], f[x][c])\n",
    "                if indeg[y] == 0:\n",
    "                    q.append(y)\n",
    "\n",
    "        if found!=n:\n",
    "            return -1\n",
    "\n",
    "        max_res = 0\n",
    "        for i in range(n):\n",
    "            max_res = max(max_res, max(f[i]))\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n  = len(colors)\n",
    "        graph = collections.defaultdict(list)\n",
    "        f = [[0] * 26 for _ in range(n)]\n",
    "        res = 0\n",
    "        ins = [0] * n\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            ins[edge[1]] += 1\n",
    "         \n",
    "        q = collections.deque()\n",
    "        for i in range(n):\n",
    "            if ins[i] == 0:\n",
    "                q.append(i)\n",
    "                \n",
    "        if len(q) == 0:\n",
    "            return -1\n",
    "        count = 0\n",
    "        while q:\n",
    "            count += 1\n",
    "            h = q.popleft()\n",
    "            f[h][ord(colors[h]) - ord('a')] += 1\n",
    "            for node in graph[h]:\n",
    "                ins[node] -= 1\n",
    "                if ins[node] == 0:\n",
    "                    q.append(node)\n",
    "                for i in range(26):\n",
    "                    f[node][i] = max(f[node][i], f[h][i])\n",
    "        if count != n:\n",
    "            return -1\n",
    "        for i in range(n):\n",
    "            res = max(res, max(f[i]))\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        \"\"\" TopSort + DP \n",
    "        State tran: \n",
    "            dp[v][j] = max(dp[curr_node][j], dp[v][j])\n",
    "        \"\"\"\n",
    "\n",
    "        # uniG \n",
    "        G = collections.defaultdict(list)\n",
    "        indeg = collections.defaultdict(int)\n",
    "        n = len(colors)\n",
    "\n",
    "        # init G/indeg \n",
    "        for u, v in edges:\n",
    "            G[u].append(v)\n",
    "            indeg[v] += 1 \n",
    "\n",
    "        que = deque([i for i in range(n) if i not in indeg])\n",
    "        dp =[ [0]*26 for _ in range(n)]  # max color number is 26 \n",
    "        while que:\n",
    "            curr_node = que.popleft()\n",
    "            dp[curr_node][ord(colors[curr_node]) - ord('a')] += 1  # color update\n",
    "            for v in G[curr_node]:\n",
    "                for j in range(26):\n",
    "                    dp[v][j] = max(dp[curr_node][j], dp[v][j])\n",
    "                indeg[v] -= 1  # indegree update \n",
    "                if not indeg[v]:\n",
    "                    que.append(v)\n",
    "\n",
    "        # check the circle \n",
    "        if sum(list(indeg.values())) != 0:\n",
    "            return -1 \n",
    "\n",
    "        return max( max(i) for i in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        degrees = [0] * n\n",
    "        rdegrees = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        rg = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            degrees[y]+=1\n",
    "            rdegrees[x]+=1\n",
    "            g[x].append(y)\n",
    "            rg[y].append(x)         #*     注意下一行的缩进-------------------------------------\n",
    "        rleaf = deque()\n",
    "        for i, d in enumerate(rdegrees):\n",
    "            if d == 0:\n",
    "                rleaf.append(i)     #*     注意下一行的缩进-------------------------------------\n",
    "        dp = [[0] * 26 for _ in range(n)]\n",
    "        while(rleaf):\n",
    "            rlf = rleaf.popleft()\n",
    "            for node in g[rlf]:\n",
    "                for c in range(26):\n",
    "                    dp[rlf][c] = max(dp[rlf][c], dp[node][c])     #*     注意下一行的缩进-------------------------------------\n",
    "            dp[rlf][ord(colors[rlf]) - ord('a')] += 1\n",
    "            for node in rg[rlf]:\n",
    "                rdegrees[node]-=1\n",
    "                if rdegrees[node]==0:\n",
    "                    rleaf.append(node)         #*     注意下一行的缩进-------------------------------------\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if rdegrees[i]!=0:\n",
    "                return -1\n",
    "            for j in range(26):\n",
    "                ans = max(ans, dp[i][j])      #*     注意下一行的缩进-------------------------------------\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        colors = list(colors)\n",
    "        colorToindex = []\n",
    "        for i in colors:\n",
    "            colorToindex.append(ord(i)-ord('a'))\n",
    "        n = len(colors)\n",
    "        indeg = [0]*n\n",
    "        graph = defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            indeg[j] +=1\n",
    "            graph[i].append(j)\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                q.append(i)\n",
    "        dp = [[0]*26 for _ in range(n)]\n",
    "        vis = set(q)\n",
    "        while q:\n",
    "            t = q\n",
    "            q = []\n",
    "            for node in t:\n",
    "                dp[node][colorToindex[node]] +=1\n",
    "                for nextnode in graph[node]:\n",
    "                    if nextnode in vis:\n",
    "                        continue\n",
    "                    indeg[nextnode] -=1\n",
    "                    for i in range(26):\n",
    "                        dp[nextnode][i] = max(dp[nextnode][i],dp[node][i])\n",
    "                    if indeg[nextnode] == 0:\n",
    "                        vis.add(nextnode)\n",
    "                        q.append(nextnode)\n",
    "        if len(vis) != n:\n",
    "            return -1\n",
    "        max_val = 0\n",
    "        for i in range(n):\n",
    "            for j in range(26):\n",
    "                max_val = max(max_val,dp[i][j])\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = defaultdict(list)\n",
    "        indegree = [0] * n\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            indegree[v] += 1\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "        ans = 0\n",
    "        dp = [Counter() for _ in range(n)]\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            dp[x][colors[x]] += 1\n",
    "            ans = max(ans, max(dp[x].values()))\n",
    "            for y in g[x]:\n",
    "                indegree[y] -= 1\n",
    "                for color, cnt in dp[x].items():\n",
    "                    dp[y][color] = max(dp[y][color], cnt)\n",
    "                if indegree[y] == 0:\n",
    "                    q.append(y)\n",
    "        return ans if sum(indegree) == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        in_degree, f, graph, dp = [0] * (n := len(colors)), lambda x: ord(x) - ord('a'), defaultdict(set), [[0] * 26 for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            in_degree[v] += 1\n",
    "        q = [u for u in range(n) if not in_degree[u]]\n",
    "        head, tail, result = 0, len(q), 0\n",
    "        while head < tail:\n",
    "            dp[u := q[head]][f(colors[u])] += 1\n",
    "            if not graph[u]:\n",
    "                result = max(result, *dp[u])\n",
    "            for v in graph[u]:\n",
    "                in_degree[v] -= 1\n",
    "                for ch in range(26):\n",
    "                    dp[v][ch] = max(dp[v][ch], dp[u][ch])\n",
    "                if not in_degree[v]:\n",
    "                    q.append(v)\n",
    "                    tail += 1\n",
    "            head += 1\n",
    "        return result if tail == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        indegree = Counter()\n",
    "        dg = defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            if a == b: return -1\n",
    "            dg[a].add(b)\n",
    "            indegree[b] += 1\n",
    "\n",
    "        dp = [[0] * 26 for _ in range(n)]\n",
    "        qu = deque(i for i in range(n) if indegree[i] == 0)\n",
    "        while qu:\n",
    "            i = qu.popleft()\n",
    "            dp[i][ord(colors[i]) - 97] += 1\n",
    "            for nt in dg[i]:\n",
    "                indegree[nt] -= 1\n",
    "                if indegree[nt] == 0:\n",
    "                    qu.append(nt)\n",
    "                for j, c in enumerate(dp[i]):\n",
    "                    dp[nt][j] = max(dp[nt][j], c)\n",
    "\n",
    "        if any(x > 0 for x in indegree.values()):\n",
    "            # print(indegree)\n",
    "            return -1\n",
    "        \n",
    "        return max(max(a) for a in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections \n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        l  = len(colors)\n",
    "        # 入度矩阵\n",
    "        indegree  = [0 for _ in range(l)]\n",
    "        ans = collections.defaultdict(set)\n",
    "        \n",
    "        # 拓扑排序建图\n",
    "        for s,e in edges:\n",
    "            ans[s].add(e)\n",
    "            indegree[e]+=1\n",
    "\n",
    "        deq  = collections.deque()\n",
    "        \n",
    "        # 颜色值 dp\n",
    "        # dp 设置矩阵\n",
    "        dp =[[0 for _ in range(26)] for _ in range(l)]\n",
    "        \n",
    "        \n",
    "        # deq\n",
    "        for i in range(l):\n",
    "            if indegree[i] == 0:\n",
    "                deq.append(i)\n",
    "\n",
    "        while deq:\n",
    "            node = deq.popleft()\n",
    "            # 节点颜色值\n",
    "            dp[node][ord(colors[node]) - ord('a')]+=1\n",
    "            for v in ans[node]:\n",
    "                for k in range(26):\n",
    "                    dp[v][k] = max(dp[node][k],dp[v][k])\n",
    "                indegree[v]-=1\n",
    "                if indegree[v] == 0:\n",
    "                    deq.append(v)\n",
    "\n",
    "        if sum(indegree)>0:\n",
    "            return -1\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                res  = max(res,dp[i][j])\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "#         l = len(colors)\n",
    "#         d = collections.defaultdict(set)#子节点集合\n",
    "#         indegree = [0 for i in range(l)]#入度\n",
    "#         for s, e in edges:\n",
    "#             d[s].add(e)\n",
    "#             indegree[e] += 1\n",
    "#         deq = collections.deque()#队列\n",
    "#         dp = [[0 for i in range(26)] for j in range(l)]#最大颜色值dp\n",
    "#         for i in range(l):\n",
    "#             if indegree[i] == 0:#如果为链头\n",
    "#                 deq.append(i)#加入队列\n",
    "#         while deq:\n",
    "#             i = deq.popleft()\n",
    "#             dp[i][ord(colors[i]) - ord(\"a\")] += 1#增加颜色值\n",
    "#             for j in d[i]:#后续子节点\n",
    "#                 for k in range(26):#更新子节点的最大值\n",
    "#                     dp[j][k] = max(dp[i][k], dp[j][k])\n",
    "#                 indegree[j] -= 1#更新入度\n",
    "#                 if indegree[j] == 0:#当入度为0则无后续路径\n",
    "#                     deq.append(j)#加入队列\n",
    "#         if sum(indegree) > 0:#如果未遍历完，则存在环\n",
    "#             return -1\n",
    "#         return max([max(i) for i in dp])#否则不存在环，每个节点的最大颜色值的最大值即是结果\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        colors = [ord(c) - ord('a') for c in colors]\n",
    "        maps = {_:set() for _ in range(n)}\n",
    "        dp = [[0 for _ in range(26)] for _ in range(n)]\n",
    "        indegree = [0 for _ in range(n)]\n",
    "        order = []\n",
    "        pointer = 0\n",
    "        for edge in edges:\n",
    "            maps[edge[0]].add(edge[1])\n",
    "            indegree[edge[1]] += 1\n",
    "        q = []\n",
    "        counter = 0\n",
    "        for i in range(n):\n",
    "            if not indegree[i]:\n",
    "                q.append(i)\n",
    "        \n",
    "        while q:\n",
    "            counter += 1\n",
    "            now = q.pop(0)\n",
    "            dp[now][colors[now]] += 1\n",
    "            for y in maps[now]:\n",
    "                indegree[y] -= 1\n",
    "                for color in range(26):\n",
    "                    dp[y][color] = max(dp[y][color], dp[now][color])\n",
    "                if not indegree[y]:\n",
    "                    q.append(y)\n",
    "        if counter != n:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans, max(dp[i]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(colors)\n",
    "        # init graph, indegree\n",
    "        graph = defaultdict(set)\n",
    "        indegree = defaultdict(int)\n",
    "        dp = defaultdict(lambda :defaultdict(int))\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            indegree[b] += 1\n",
    "        \n",
    "        zeroIndegree = list(filter(lambda i: indegree[i]==0, range(n)))\n",
    "        visited = 0\n",
    "        ans = 0\n",
    "        while zeroIndegree:\n",
    "            curr = zeroIndegree.pop()\n",
    "            visited +=1\n",
    "            dp[curr][colors[curr]] += 1\n",
    "            # print('curr=',curr,dp[curr])\n",
    "            ans = max(ans, max(dp[curr].values()))\n",
    "            for target in graph[curr]:\n",
    "                indegree[target] -= 1\n",
    "                if indegree[target] == 0: zeroIndegree.append(target)\n",
    "                for ckey in dp[curr]:\n",
    "                    # print('dp[',target,'][',ckey,']',dp[target][ckey])\n",
    "                    dp[target][ckey] = max(dp[target][ckey], dp[curr][ckey])\n",
    "                # print('target=',target,dp[target])\n",
    "\n",
    "        return -1 if visited<n else ans\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        :type colors: str\n",
    "        :type edges: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(colors)\n",
    "        ind = [0] * n\n",
    "        g = {index : set() for index in range(n)}\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            ind[y] += 1\n",
    "        \n",
    "        f = {index : {} for index in range(n)}\n",
    "        q = []\n",
    "        for index in range(n):\n",
    "            if ind[index] == 0:\n",
    "                q.append(index)\n",
    "                f[index][colors[index]] = 1\n",
    "\n",
    "        l = 0\n",
    "        r = len(q)\n",
    "        res = 1\n",
    "        while l < r:\n",
    "            now = q[l]\n",
    "            l += 1\n",
    "            for next in g[now]:\n",
    "                for color in f[now]:\n",
    "                    cnt = f[now][color]\n",
    "                    f[next][color] = max(f[next].get(color, 0), cnt)\n",
    "\n",
    "                ind[next] -= 1\n",
    "                if ind[next] == 0:\n",
    "                    q.append(next)\n",
    "                    r += 1\n",
    "                    f[next][colors[next]] = f[next].get(colors[next], 0) + 1\n",
    "                    res = max(res, max(f[next].values()))\n",
    "        \n",
    "        if len(q) != n:\n",
    "            return -1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "\n",
    "        graph = {i: set() for i in range(n)}\n",
    "        indegree = {i: 0 for i in range(n)}\n",
    "\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            indegree[v] += 1\n",
    "        \n",
    "        stack = []\n",
    "\n",
    "        for u in indegree:\n",
    "            if indegree[u] == 0:\n",
    "                stack.append(u)\n",
    "        \n",
    "        for u in stack:\n",
    "            indegree.pop(u)\n",
    "\n",
    "        dp = [[0 for i in range(26)] for j in range(n)]\n",
    "        ans = 0\n",
    "\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            dp[cur][ord(colors[cur]) - 97] += 1\n",
    "            for u in graph[cur]:\n",
    "                for i in range(26):\n",
    "                    dp[u][i] = max(dp[u][i], dp[cur][i])\n",
    "                indegree[u] -= 1\n",
    "                if indegree[u] == 0:\n",
    "                    stack.append(u)\n",
    "                    indegree.pop(u)\n",
    "        \n",
    "        if len(indegree) > 0:\n",
    "            return -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            ans = max(ans, max(dp[i]))\n",
    "        \n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        deg = [0] * n\n",
    "        temp = copy.deepcopy(deg)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            a, b = edge\n",
    "            deg[b] += 1\n",
    "            g[a].append(b)\n",
    "\n",
    "        qu = deque()\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                qu.append(i)\n",
    "        while qu:\n",
    "            a = qu.popleft()\n",
    "            for b in g[a]:\n",
    "                deg[b] -= 1\n",
    "                if deg[b] == 0:\n",
    "                    qu.append(b)\n",
    "        for i in range(n):\n",
    "            if deg[i] != 0:\n",
    "                return -1\n",
    "\n",
    "        cnt = {}\n",
    "        vis = [0] * n\n",
    "\n",
    "        def get(u):\n",
    "            if vis[u]:\n",
    "                return\n",
    "            cnt[u] = defaultdict(int)\n",
    "            for v in g[u]:\n",
    "                get(v)\n",
    "                for key, c in cnt[v].items():\n",
    "                    cnt[u][key] = max(cnt[u][key], c)\n",
    "            cnt[u][colors[u]] += 1\n",
    "            vis[u] = 1\n",
    "\n",
    "        ans = 0\n",
    "        deg = temp\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                get(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            for k, c in cnt[i].items():\n",
    "                ans = max(c, ans)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n=len(colors)\n",
    "        ad={i:[] for i in range(n)}\n",
    "        ind={i:0 for i in range(n)}\n",
    "        cnt={}\n",
    "        dp=[[0]*26 for _ in range(n)]\n",
    "        for s,e in edges:\n",
    "            ind[s]+=1\n",
    "            ad[e].append(s)\n",
    "        stack=[]\n",
    "        #print(dp)\n",
    "        for x in ind:\n",
    "            if ind[x]==0:\n",
    "               # print(ord(colors[x])-ord(\"a\"))\n",
    "                stack.append(x)\n",
    "                \n",
    "        if len(stack)==0:\n",
    "            return -1\n",
    "        \n",
    "     #   print(ad)\n",
    "        #print(ind)\n",
    "\n",
    "        \n",
    "        while stack:\n",
    "            cur=stack.pop(0)\n",
    "            dp[cur][ord(colors[cur])-ord(\"a\")]+=1\n",
    "            #print(ad[cur])\n",
    "            for nex in ad[cur]:\n",
    "                #print(nex)\n",
    "                ind[nex]-=1\n",
    "                for k in range(26):\n",
    "                    dp[nex][k]=max(dp[cur][k],dp[nex][k])\n",
    "\n",
    "                if ind[nex]==0:\n",
    "                    stack.append(nex)\n",
    "        if sum(ind.values()) > 0:\n",
    "            return -1\n",
    "        print(dp)\n",
    "        return max([max(i) for i in dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict, deque\n",
    "\n",
    "def build_graph(edges, bidirectional=False, costs=None):\n",
    "    g = defaultdict(list)\n",
    "    if costs:\n",
    "        for (a,b),cost in zip(edges, costs):\n",
    "            g[a].append((b,cost))\n",
    "            if bidirectional:\n",
    "                g[b].append((a,cost))\n",
    "    else:\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            if bidirectional:\n",
    "                g[b].append(a)\n",
    "    return g\n",
    "\n",
    "def topological_sort(map_from_node_to_nodes, all_nodes=set()):\n",
    "    # leetcode.com/problems/course-schedule-ii/\n",
    "    # leetcode.com/problems/course-schedule/\n",
    "    indegree_counter = defaultdict(int)\n",
    "    for lst in map_from_node_to_nodes.values():\n",
    "        for v in lst:\n",
    "            indegree_counter[v] += 1\n",
    "\n",
    "    if not all_nodes:  # assume all nodes are found in the map\n",
    "        all_nodes = set(indegree_counter.keys()) | set(map_from_node_to_nodes)\n",
    "\n",
    "    dq = deque([node for node in all_nodes if node not in indegree_counter])\n",
    "\n",
    "    res = []\n",
    "    while dq:\n",
    "        cur = dq.popleft()\n",
    "        res.append(cur)\n",
    "        for nex in map_from_node_to_nodes[cur]:\n",
    "            indegree_counter[nex] -= 1\n",
    "            if indegree_counter[nex] == 0:\n",
    "                dq.append(nex)\n",
    "    return res if len(res) == len(all_nodes) else []\n",
    "\n",
    "\n",
    "def detect_cycle(map_from_node_to_nodes):\n",
    "    if not map_from_node_to_nodes:\n",
    "        return False\n",
    "    # leetcode.com/problems/course-schedule/\n",
    "    return topological_sort(map_from_node_to_nodes) == []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        g = build_graph(edges)\n",
    "        if detect_cycle(g):\n",
    "            return -1\n",
    "\n",
    "        # consider all colors\n",
    "        # print(g)\n",
    "        \n",
    "        abc = {ab:i for i,ab in enumerate(\"abcdefghijklmnopqrstuvwxyz\")}\n",
    "        colors = [abc[x] for x in colors]\n",
    "        # print(colors)\n",
    "        maxres = 0\n",
    "        \n",
    "        for col in range(26):\n",
    "            @functools.lru_cache(maxsize=10**5)\n",
    "            def dfs(cur):\n",
    "                val = 1 if colors[cur] == col else 0\n",
    "                length = val\n",
    "                for nex in g[cur]:\n",
    "                    length = max(length, dfs(nex) + val)\n",
    "                return length\n",
    "        \n",
    "            # print(col, [dfs(start) for start in colors])\n",
    "            res = max(dfs(start) for start in range(len(colors)))\n",
    "            maxres = max(maxres, res)\n",
    "            \n",
    "        return maxres"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(colors)\n",
    "        inDeg = {k : 0 for k in range(n)}\n",
    "        # pre[cur]是cur的上个节点\n",
    "        # 二维数组不可以直接*n 初始化陷阱\n",
    "        pre = [[] for i in range(n)]\n",
    "\n",
    "        # 每步每个颜色可以出现的最大值\n",
    "        node_colors = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "\n",
    "        q = []\n",
    "\n",
    "        for item in edges:\n",
    "            inDeg[item[1]] += 1\n",
    "\n",
    "        max_color = 0\n",
    "        for k, v in inDeg.items():\n",
    "            if inDeg[k] == 0:\n",
    "                q.append(k)\n",
    "       \n",
    "        for st in q:\n",
    "            del inDeg[st]\n",
    "\n",
    "        ne = defaultdict(lambda: [])\n",
    "        # 找到下一个相关的点，这里就是遍历数组，如果数组的[i][0] == cur就证明这个点有关系.\n",
    "        m = len(edges)\n",
    "        for i in range(m):\n",
    "            cur = edges[i][0]\n",
    "            next_node = edges[i][1]\n",
    "                # 这里会被迭代但是我感觉好像没有问题 0->1->2和0->2，经过一个1可以联通，多1并不会影响最大颜色数\n",
    "                # 有问题\n",
    "            ne[cur].append(next_node)\n",
    "\n",
    "            \n",
    "        max_path_color = 0\n",
    "        while len(q) > 0:\n",
    "            cur = q.pop(0)\n",
    "            if len(pre[cur]) == 0:\n",
    "                node_colors[cur][colors[cur]] = 1\n",
    "            for pre_node in pre[cur]:\n",
    "            \n",
    "                # 如果cur和上一个点的colors分布的哪个值相等？更新并算最大值\n",
    "            \n",
    "                # 看下pre node里面所有的颜色\n",
    "                # 看下cur节点的颜色\n",
    "                cur_color = colors[cur]\n",
    "                # 值传递，不是引用传递\n",
    "                # node_colors[cur] = node_colors[pre_node].copy()\n",
    "                # 要更新所有的最大颜色,包括自己的颜色，这里要注意，这个点不是开头的点，因此有时间限制\n",
    "                node_colors[cur][cur_color] = max(1, node_colors[cur][cur_color])\n",
    "                for k, v in node_colors[pre_node].items():\n",
    "                    node_colors[cur][k] = max(node_colors[cur][k], v)\n",
    "                    if k == cur_color:\n",
    "                        node_colors[cur][k] = max(node_colors[cur][k], v + 1)\n",
    "                # 在其他分支上的最大值\n",
    "                # if pre_node == 4 and cur == 6:\n",
    "                #     print(cur_color)\n",
    "                #     print( node_colors[pre_node][cur_color], \"?\")\n",
    "\n",
    "            max_path_color = max(max_path_color, max(node_colors[cur].values()))\n",
    "\n",
    "            # 找到下一个相关的点，这里就是遍历数组，如果数组的[i][0] == cur就证明这个点有关系.\n",
    "            for next_node in ne[cur]:\n",
    "                pre[next_node].append(cur)\n",
    "                inDeg[next_node] -= 1\n",
    "                if inDeg[next_node] == 0:\n",
    "                    q.append(next_node)\n",
    "                    del inDeg[next_node]\n",
    "        #     m = len(edges)\n",
    "        #     for i in range(m):\n",
    "        #         if edges[i][0] == cur:\n",
    "        #             next_node = edges[i][1]\n",
    "        #             # 这里会被迭代但是我感觉好像没有问题 0->1->2和0->2，经过一个1可以联通，多1并不会影响最大颜色数\n",
    "        #             # 有问题\n",
    "        #             pre[next_node].append(cur)\n",
    "\n",
    "        #             inDeg[next_node] -= 1\n",
    "        #             if inDeg[next_node] == 0:\n",
    "        #                 q.append(next_node)\n",
    "        #                 del inDeg[next_node]\n",
    "        # # print(node_colors[95])\n",
    "                \n",
    "        if len(inDeg) > 0:\n",
    "            return -1\n",
    "\n",
    "        return max_path_color\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        tcon = {}\n",
    "        fcon = {}\n",
    "        node_set = set()\n",
    "\n",
    "        if not edges:\n",
    "            return 1\n",
    "        \n",
    "        for edge in edges:\n",
    "            if not edge[0] in node_set:\n",
    "                node_set.add(edge[0])\n",
    "                tcon[edge[0]] = []\n",
    "                fcon[edge[0]] = []\n",
    "            if not edge[1] in node_set:\n",
    "                node_set.add(edge[1])\n",
    "                tcon[edge[1]] = []\n",
    "                fcon[edge[1]] = []\n",
    "\n",
    "        for edge in edges:\n",
    "            tcon[edge[0]].append(edge[1])\n",
    "            fcon[edge[1]].append(edge[0])\n",
    "        \n",
    "        fcount = {}\n",
    "        tcount = {}\n",
    "        stack = []\n",
    "        for k, v in tcon.items():\n",
    "            if v == []:\n",
    "                stack.append(k)\n",
    "            tcount[k] = len(v)\n",
    "        for k, v in fcon.items():\n",
    "            fcount[k] = len(v)\n",
    "        \n",
    "\n",
    "        dic = {}\n",
    "        for node in stack:\n",
    "            dic[node] = collections.defaultdict(int)\n",
    "            dic[node][colors[node]] += 1\n",
    "        \n",
    "        visited = set()\n",
    "        final_dict = {}\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            visited.add(node)\n",
    "            for fnode in fcon[node]:\n",
    "                if fnode not in dic:\n",
    "                    dic[fnode] = dic[node].copy()\n",
    "                else:\n",
    "                    dic[fnode] = self.helper(dic[fnode], dic[node])\n",
    "                tcount[fnode] -= 1\n",
    "                if tcount[fnode] == 0:\n",
    "                    stack.append(fnode)\n",
    "                    dic[fnode][colors[fnode]] += 1\n",
    "                    final_dict = self.helper(final_dict, dic[fnode])\n",
    "                # print(dic[fnode])\n",
    "\n",
    "        if len(visited) < len(node_set):\n",
    "            return -1\n",
    "\n",
    "        return max(final_dict.values())\n",
    "    \n",
    "    def helper(self, dic1, dic2):\n",
    "        for k, v in dic2.items():\n",
    "            if k not in dic1:\n",
    "                dic1[k] = v\n",
    "            elif dic1[k] < v:\n",
    "                dic1[k] = v\n",
    "        return dic1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        N = len(colors)\n",
    "        G, IN = [[] for i in range(N)], [0] * N\n",
    "        for a, b in edges:\n",
    "            G[a].append(b)\n",
    "            IN[b] += 1\n",
    "        \n",
    "        q = [i for i in range(N) if IN[i] == 0]\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            tmp = []\n",
    "            cnt += len(q)\n",
    "            for n in q:\n",
    "                for m in G[n]:\n",
    "                    IN[m] -= 1\n",
    "                    if IN[m] == 0: tmp.append(m)\n",
    "            q = tmp\n",
    "        \n",
    "        if cnt < N: return -1\n",
    "\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            ans = [0] * 26\n",
    "            for m in G[n]:\n",
    "                lis = dfs(m)\n",
    "                ans = [a if a > b else b for a, b in zip(ans, lis)]\n",
    "            ans[ord(colors[n]) - 97] += 1\n",
    "            return ans[:]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            if not IN[i]:\n",
    "                if (val := max(dfs(i))) > ans: ans = val\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter, CycleError\r\n",
    "class Solution:\r\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\r\n",
    "        n = len(colors)\r\n",
    "        res = 0\r\n",
    "        # dp[i][j] := highest frequency of color j in all path arriving node i\r\n",
    "        dp = [[0] * 26 for _ in range(n)]\r\n",
    "        after = [[] for _ in range(n)]\r\n",
    "        ts = TopologicalSorter()\r\n",
    "\r\n",
    "        for node in range(n):\r\n",
    "            ts.add(node)\r\n",
    "        for u, v in edges:\r\n",
    "            ts.add(v, u)\r\n",
    "            after[u].append(v)\r\n",
    "        \r\n",
    "        try:\r\n",
    "            ts.prepare()\r\n",
    "        except CycleError:\r\n",
    "            return -1\r\n",
    "        \r\n",
    "        while ts.is_active():\r\n",
    "            for node in ts.get_ready():\r\n",
    "                dp[node][ord(colors[node]) - 97] += 1\r\n",
    "                res = max(res, dp[node][ord(colors[node]) - 97])\r\n",
    "                for nxt in after[node]:\r\n",
    "                    for i in range(26):\r\n",
    "                        dp[nxt][i] = max(dp[nxt][i], dp[node][i])\r\n",
    "\r\n",
    "                ts.done(node)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import deque, defaultdict\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        if not edges:\n",
    "            return 1\n",
    "        in_vertex = defaultdict(set)\n",
    "        to_vertex = defaultdict(set)\n",
    "        degree_ver = defaultdict(set)\n",
    "        ver_degree = defaultdict(int)\n",
    "        for p, q in edges:\n",
    "            to_vertex[p].add(q)\n",
    "            in_vertex[q].add(p)\n",
    "            in_vertex[p]\n",
    "            ver_degree[q] += 1\n",
    "            ver_degree[p]\n",
    "        for p, tar_set in in_vertex.items():\n",
    "            degree_ver[len(tar_set)].add(p)\n",
    "        color = set(colors)\n",
    "        dp = [defaultdict(int) for i in colors]\n",
    "        for i, c in enumerate(colors):\n",
    "            dp[i][c] = 1\n",
    "        res = 0\n",
    "        while degree_ver[0]:\n",
    "            vertex = degree_ver[0].pop()\n",
    "            clr = colors[vertex]\n",
    "            for p in in_vertex[vertex]:\n",
    "                for c in color:\n",
    "                    dp[vertex][c] = max(dp[vertex][c], dp[p][c] + 1 if c == clr else dp[p][c])\n",
    "                    res = max(res, dp[vertex][c])\n",
    "            for p in to_vertex[vertex]:\n",
    "                degree_ver[ver_degree[p]].remove(p)\n",
    "                ver_degree[p] -= 1\n",
    "                degree_ver[ver_degree[p]].add(p)\n",
    "        for k, v in degree_ver.items():\n",
    "            if k != 0 and v:\n",
    "                return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for i, j in edges:\n",
    "            graph[i].append(j)\n",
    "            indegree[j] += 1\n",
    "        \n",
    "        q = [x for x in range(n) if indegree[x] == 0]\n",
    "        d = 0\n",
    "        while q:\n",
    "            nx = []\n",
    "            d += len(q)\n",
    "            for i in q:\n",
    "                for j in graph[i]:\n",
    "                    indegree[j] -= 1\n",
    "                    if indegree[j] == 0:\n",
    "                        nx.append(j)\n",
    "            q = nx\n",
    "        if d != n:\n",
    "            return -1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            res = [0] * 26\n",
    "            for i in graph[node]:\n",
    "                son = dfs(i)\n",
    "                res = [max(x1, x2) for x1, x2 in zip(res, son)]\n",
    "            res[ord(colors[node]) - ord('a')] += 1;\n",
    "            return res\n",
    "        \n",
    "        ans = [0] * 26\n",
    "        for i in range(n):\n",
    "            ans = [max(x1, x2) for x1, x2 in zip(ans, dfs(i))]\n",
    "\n",
    "        return max(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        # 求最大颜色数，需要会统计出每条路径最大的数\n",
    "        # 只要路径不串在一起，就可以用一个队列解决\n",
    "        n = len(colors)\n",
    "        m = len(edges)\n",
    "        value = defaultdict(lambda: defaultdict(lambda: 0))\n",
    "        q = []\n",
    "\n",
    "        inDeg = {k: 0 for k in range(n)}\n",
    "        pre = [[] for i in range(n)]\n",
    "        ne = [[] for i in range(n)]\n",
    "\n",
    "        for item in edges:\n",
    "            ne[item[0]].append(item[1])\n",
    "            pre[item[1]].append(item[0])\n",
    "            inDeg[item[1]] += 1\n",
    "\n",
    "        for i in inDeg.keys():\n",
    "            if inDeg[i] == 0:\n",
    "                # 先拿到全部的起点\n",
    "                q.append(i)\n",
    "\n",
    "        for item in q:\n",
    "            del inDeg[item]\n",
    "\n",
    "        max_color = 0\n",
    "        while len(q) > 0:\n",
    "            cur = q.pop(0)\n",
    "            c = colors[cur]\n",
    "            \n",
    "            if len(pre[cur]) == 0:\n",
    "              \n",
    "                # 证明是头节点,不可能有其他最大值，也只能有一个颜色\n",
    "                value[cur][c] = 1\n",
    "            else:\n",
    "                # 不是头结点，此时需要考虑前一个节点的每个颜色的最大值\n",
    "                for pre_node in pre[cur]:\n",
    "                    for k, v in value[pre_node].items():\n",
    "                        value[cur][k] = max(value[pre_node][k] + (1 if k == c else 0), value[cur][k])\n",
    "                    if c not in value[pre_node].keys():\n",
    "                        value[cur][c] = max(value[cur][c], 1)\n",
    "            \n",
    "            max_color = max(max(value[cur].values()), max_color)\n",
    "\n",
    "            for next_node in ne[cur]:\n",
    "                inDeg[next_node] -= 1\n",
    "                if inDeg[next_node] == 0:\n",
    "                    q.append(next_node)\n",
    "                    del inDeg[next_node]\n",
    "\n",
    "        if len(inDeg) != 0:\n",
    "            return -1\n",
    "        print(value)\n",
    "        return max_color\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from graphlib import TopologicalSorter\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        degree = [0] * n\n",
    "        table = defaultdict(list)\n",
    "        for v1, v2 in edges:\n",
    "            degree[v2] += 1\n",
    "            table[v1].append(v2)\n",
    "        \n",
    "        ts = TopologicalSorter()\n",
    "        for x in range(n):\n",
    "            ts.add(x)\n",
    "        for x, y in edges:\n",
    "            ts.add(y, x)\n",
    "        try:\n",
    "            for i, x in enumerate(ts.static_order()):\n",
    "                pass\n",
    "        except:\n",
    "            return -1\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(cur, color):\n",
    "            rnt = int(colors[cur] == color)\n",
    "            for nxt in table[cur]:\n",
    "                rnt = max(rnt, dfs(nxt, color) + int(colors[cur] == color))\n",
    "            return rnt\n",
    "        s = set(colors)\n",
    "        for i in range(n):\n",
    "            for color in s:\n",
    "                ans = max(ans, dfs(i, color))\n",
    "        # for i in range(n):\n",
    "        #     for j in range(26):\n",
    "        #         ans = max(ans, dfs(i, chr(j + ord('a'))))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        dct = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            degree[b] += 1\n",
    "            dct[a].append(b)\n",
    "\n",
    "        n = len(colors)\n",
    "        stack = [node for node in range(n) if not degree[node]]\n",
    "        visit = [0]*n\n",
    "        for i in stack:\n",
    "            visit[i] = 1\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i in stack:\n",
    "                for j in dct[i]:\n",
    "                    degree[j] -= 1\n",
    "                    if not degree[j]:\n",
    "                        nex.append(j)\n",
    "                        visit[j] = 1\n",
    "            stack = nex\n",
    "\n",
    "        if sum(visit) != n:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            res = [0]*26\n",
    "            res[ord(colors[x])-ord(\"a\")] += 1\n",
    "            add = [0]*26\n",
    "            for y in dct[x]:\n",
    "                nex = dfs(y)\n",
    "                for p in range(26):\n",
    "                    add[p] = add[p] if add[p] > nex[p] else nex[p]\n",
    "            for p in range(26):\n",
    "                res[p] += add[p]\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not degree[i]:\n",
    "                cur = dfs(i)\n",
    "                ans = max(ans, max(cur))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        # 图算法\n",
    "        if len(edges) == 0: return 1\n",
    "        adjacent = {}\n",
    "        for u , v in edges:\n",
    "            if u in adjacent:\n",
    "                adjacent[u].append(v)\n",
    "            else:\n",
    "                adjacent[u] = [v]\n",
    "        \n",
    "        # topology\n",
    "        record = [0] * len(colors)\n",
    "        self.timestamp = 7\n",
    "\n",
    "        for i in range(len(record)):\n",
    "            if record[i] == 0:\n",
    "                record[i] = 1\n",
    "                if not self.dfs(i , record , adjacent): return -1\n",
    "        \n",
    "        topology = sorted( enumerate(record) , key= lambda x: -x[1] ) # 父在子前\n",
    "        count_color = {}\n",
    "        COLOR_NUM = 0\n",
    "        for s in colors:\n",
    "            if s not in count_color:\n",
    "                count_color[s] = COLOR_NUM\n",
    "                COLOR_NUM += 1\n",
    "\n",
    "        dp = [[0]* COLOR_NUM for _ in range(len(record))]\n",
    "        arc_adjacent = {}\n",
    "        for u , v in edges:\n",
    "            if v in arc_adjacent:\n",
    "                arc_adjacent[v].append(u)\n",
    "            else:\n",
    "                arc_adjacent[v] = [u]  \n",
    "        \n",
    "        maxi = 0\n",
    "        for j in range(len(record)):\n",
    "            node = topology[j][0]\n",
    "            tmp = 0\n",
    "            for color in range( COLOR_NUM ):\n",
    "                extra = 1 if color == count_color[colors[node]] else 0\n",
    "                if node in arc_adjacent:\n",
    "                    for parent in arc_adjacent[node]:\n",
    "                        dp[node][color] = max( dp[node][color]  , dp[parent][color] + extra)\n",
    "                else:\n",
    "                    dp[node][color] = extra\n",
    "                maxi = max(maxi , dp[node][color] )\n",
    "        return maxi   \n",
    "\n",
    "    def dfs(self , node , record ,adjacent):\n",
    "        if node not in adjacent:\n",
    "            self.timestamp += 1\n",
    "            record[node] = self.timestamp\n",
    "            return True\n",
    "        else:\n",
    "            for child in adjacent[node]:\n",
    "                if record[child] == 1:\n",
    "                    return False\n",
    "                elif record[child] == 0:\n",
    "                    record[child] = 1\n",
    "                    if not self.dfs(child ,record , adjacent):\n",
    "                        return False\n",
    "\n",
    "            self.timestamp += 1\n",
    "            record[node] = self.timestamp \n",
    "            return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        colors = [ord(c) - ord('a') for c in colors]\n",
    "        edges = set((tuple(x) for x in edges))\n",
    "        n = len(colors)\n",
    "        from_ = [set() for _ in range(n)]\n",
    "        to = [set() for _ in range(n)]\n",
    "        indegree = [0] * n\n",
    "        for (a, b) in edges:\n",
    "            if a == b:\n",
    "                return -1\n",
    "            from_[b].add(a)\n",
    "            to[a].add(b)\n",
    "            indegree[b] += 1\n",
    "        indegree2vertexes = [set() for _ in range(n)]\n",
    "        for (a, d) in enumerate(indegree):\n",
    "            indegree2vertexes[d].add(a)\n",
    "        ans = 0\n",
    "        dp = [[0] * 26 for _ in range(n)]\n",
    "        visited = set()\n",
    "        for _ in range(n):\n",
    "            if not indegree2vertexes[0]:\n",
    "                return -1\n",
    "            b = indegree2vertexes[0].pop()\n",
    "            for i in range(26):\n",
    "                dp[b][i] = max((dp[a][i] for a in from_[b]), default=0)\n",
    "                if i == colors[b]:\n",
    "                    dp[b][i] += 1\n",
    "                ans = max(ans, dp[b][i])\n",
    "            visited.add(b)\n",
    "            for c in to[b]:\n",
    "                if c in visited:\n",
    "                    return -1\n",
    "                indegree2vertexes[indegree[c]].remove(c)\n",
    "                indegree2vertexes[indegree[c] - 1].add(c)\n",
    "                indegree[c] -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n, m = len(colors), len(edges)\n",
    "        G = [[] for _ in range(n)]\n",
    "        degIn = [0] * n\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            degIn[b] += 1\n",
    "        state = [-1] * n\n",
    "        def dfs(i):\n",
    "            if state[i] >= 0:\n",
    "                return bool(state[i])\n",
    "            state[i] = 1\n",
    "            for j in G[i]:\n",
    "                if dfs(j):\n",
    "                    return True\n",
    "            state[i] = 0\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if dfs(i):\n",
    "                return -1\n",
    "        state.clear()\n",
    "\n",
    "        start = [i for i in range(n) if degIn[i] == 0]\n",
    "        ans = 0\n",
    "        for c in set(colors):\n",
    "            cnt = [-1] * n\n",
    "            def dfs(i):\n",
    "                if cnt[i] >= 0:\n",
    "                    return cnt[i]\n",
    "                cnt[i] = int(colors[i] == c)\n",
    "                mx = 0\n",
    "                for j in G[i]:\n",
    "                    mx = max(mx, dfs(j))\n",
    "                cnt[i] += mx\n",
    "                return cnt[i]\n",
    "            for i in start:\n",
    "                dfs(i)\n",
    "            ans = max(ans, max(cnt))\n",
    "            cnt.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TarjanCC:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_strongly_connected_component_bfs(n: int, edge: List[List[int]]) -> (int, DefaultDict[int, Set[int]], List[int]):\n",
    "        # 模板：Tarjan求解有向图的强连通分量 edge为有向边要求无自环与重边\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        out = []\n",
    "        in_stack = [0] * n\n",
    "        scc_id = 0\n",
    "        scc_node_id = defaultdict(set)\n",
    "        node_scc_id = [-1] * n\n",
    "        parent = [-1]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                        out.append(cur)\n",
    "                        in_stack[cur] = 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        if order[cur] == low[cur]:\n",
    "                            while out:\n",
    "                                top = out.pop()\n",
    "                                in_stack[top] = 0\n",
    "                                scc_node_id[scc_id].add(top)\n",
    "                                node_scc_id[top] = scc_id\n",
    "                                if top == cur:\n",
    "                                    break\n",
    "                            scc_id += 1\n",
    "\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            stack.append([nex, 0])\n",
    "                        elif in_stack[nex]:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "\n",
    "        # 建立新图\n",
    "        new_dct = [set() for _ in range(scc_id)]\n",
    "        for i in range(n):\n",
    "            for j in edge[i]:\n",
    "                a, b = node_scc_id[i], node_scc_id[j]\n",
    "                if a != b:\n",
    "                    new_dct[b].add(a)\n",
    "        new_degree = [0]*scc_id\n",
    "        for i in range(scc_id):\n",
    "            for j in new_dct[i]:\n",
    "                new_degree[j] += 1\n",
    "        # SCC的数量，分组，每个结点对应的SCC编号\n",
    "        return scc_id, scc_node_id, node_scc_id\n",
    "\n",
    "    @staticmethod\n",
    "    def get_point_doubly_connected_component_bfs(n: int, edge: List[List[int]]) -> Tuple[int, DefaultDict[int, Set[int]], List[Set[int]]]:\n",
    "        # 模板：Tarjan求解无向图的点双连通分量\n",
    "\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [False] * n\n",
    "        out = []\n",
    "        parent = [-1]*n\n",
    "        group_id = 0  # 点双个数\n",
    "        group_node = defaultdict(set)  # 每个点双包含哪些点\n",
    "        node_group_id = [set() for _ in range(n)]  # 每个点属于哪些点双，属于多个点双的点就是割点\n",
    "        child = [0]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = True\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                            # 遇到了割点（有根和非根两种）\n",
    "                            if (parent == -1 and child[cur] > 1) or (parent != -1 and low[nex] >= order[cur]):\n",
    "                                while out:\n",
    "                                    top = out.pop()\n",
    "                                    group_node[group_id].add(top[0])\n",
    "                                    group_node[group_id].add(top[1])\n",
    "                                    node_group_id[top[0]].add(group_id)\n",
    "                                    node_group_id[top[1]].add(group_id)\n",
    "                                    if top == (cur, nex):\n",
    "                                        break\n",
    "                                group_id += 1\n",
    "                            # 我们将深搜时遇到的所有边加入到栈里面，当找到一个割点的时候\n",
    "                            # 就将这个割点往下走到的所有边弹出，而这些边所连接的点就是一个点双\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if nex == parent[cur]:\n",
    "                            continue\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            out.append((cur, nex))\n",
    "                            child[cur] += 1\n",
    "                            stack.append([nex, 0])\n",
    "                        elif low[cur] > order[nex]:\n",
    "                            low[cur] = order[nex]\n",
    "                            out.append((cur, nex))\n",
    "            if out:\n",
    "                while out:\n",
    "                    top = out.pop()\n",
    "                    group_node[group_id].add(top[0])\n",
    "                    group_node[group_id].add(top[1])\n",
    "                    node_group_id[top[0]].add(group_id)\n",
    "                    node_group_id[top[1]].add(group_id)\n",
    "                group_id += 1\n",
    "        # 点双的数量，点双分组节点，每个结点对应的点双编号（割点属于多个点双）\n",
    "        return group_id, group_node, node_group_id\n",
    "\n",
    "    def get_edge_doubly_connected_component_bfs(self, n: int, edge: List[Set[int]]):\n",
    "        # 模板：Tarjan求解无向图的边双连通分量\n",
    "        _, cutting_edges = self.get_cutting_point_and_cutting_edge_bfs(n, [list(e) for e in edge])\n",
    "        for i, j in cutting_edges:\n",
    "            edge[i].discard(j)\n",
    "            edge[j].discard(i)\n",
    "\n",
    "        # 将所有的割边删掉剩下的都是边双连通分量，处理出割边，再对整个无向图进行一次BFS\n",
    "        visit = [0]*n\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            stack = [i]\n",
    "            visit[i] = 1\n",
    "            cur = [i]\n",
    "            while stack:\n",
    "                x = stack.pop()\n",
    "                for j in edge[x]:\n",
    "                    if not visit[j]:\n",
    "                        visit[j] = 1\n",
    "                        stack.append(j)\n",
    "                        cur.append(j)\n",
    "            ans.append(cur[:])\n",
    "        # 边双的节点分组\n",
    "        return ans\n",
    "\n",
    "    @staticmethod\n",
    "    def get_cutting_point_and_cutting_edge_bfs(n: int, edge: List[List[int]]) -> (Set[int], Set[Tuple[int, int]]):\n",
    "        # 模板：Tarjan求解无向图的割点和割边（也就是桥）\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        cutting_point = set()\n",
    "        cutting_edge = []\n",
    "        child = [0]*n\n",
    "        parent = [-1]*n\n",
    "        dfs_id = 0\n",
    "        for i in range(n):\n",
    "            if not visit[i]:\n",
    "                stack = [[i, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            pa = parent[cur]\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                            if low[nex] > order[cur]:\n",
    "                                cutting_edge.append((cur, nex) if cur < nex else (nex, cur))\n",
    "                            if pa != -1 and low[nex] >= order[cur]:\n",
    "                                cutting_point.add(cur)\n",
    "                            elif pa == -1 and child[cur] > 1:  # 出发点没有祖先，所以特判一下\n",
    "                                cutting_point.add(cur)\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if nex == parent[cur]:\n",
    "                            continue\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            child[cur] += 1\n",
    "                            stack.append([nex, 0])\n",
    "                        else:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "        # 割点和割边\n",
    "        return cutting_point, cutting_edge\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(colors)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        degree = [0] * n\n",
    "        for i, j in edges:\n",
    "            if i == j:\n",
    "                return -1\n",
    "            dct[i].append(j)\n",
    "            degree[j] += 1\n",
    "        scc_id, scc_node_id, node_scc_id = TarjanCC().get_strongly_connected_component_bfs(n, dct)\n",
    "        if max(Counter(node_scc_id).values()) > 1:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            res = [0]*26\n",
    "            for y in dct[x]:\n",
    "                cur = dfs(y)\n",
    "                for i in range(26):\n",
    "                    if cur[i] > res[i]:\n",
    "                        res[i] = cur[i]\n",
    "            res[ord(colors[x])-ord(\"a\")] += 1\n",
    "            xx = max(res)\n",
    "            if xx > ans:\n",
    "                ans = xx\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路\n",
    "# 1. 检测有没有cycle，如果有返回-1\n",
    "# 2. Counter 的并集 | 操作就是取两者最大值。所以做dfs遍历，对于每个子节点返回的freq取其并集，然后为自身节点的颜色freq +1 \n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "        \n",
    "        n = len(colors)\n",
    "        visiting = set()\n",
    "        visited = set()        \n",
    "        \n",
    "        # 检测环\n",
    "        def detectCycle(i):\n",
    "            if i in visited:\n",
    "                return False            \n",
    "            if i in visiting:\n",
    "                return True\n",
    "            visiting.add(i)\n",
    "            for j in graph[i]:\n",
    "                if detectCycle(j):\n",
    "                    return True\n",
    "            visiting.remove(i)\n",
    "            visited.add(i)\n",
    "            return False\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i not in visited and detectCycle(i):\n",
    "                return -1\n",
    "        \n",
    "        # 计算路径最大频率\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            freq = Counter()\n",
    "            for j in graph[i]:\n",
    "                freq = freq | dfs(j)\n",
    "            freq[colors[i]] += 1\n",
    "            return freq\n",
    "\n",
    "        freq = Counter()\n",
    "        for i in range(n):\n",
    "            freq = freq | dfs(i)\n",
    "        return freq.most_common()[0][1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        if len(colors) == 0:\n",
    "            return 0\n",
    "        if len(edges) == 0:\n",
    "            return 1\n",
    "        color_set = set()\n",
    "        for color in colors:\n",
    "            color_set.add(color)\n",
    "\n",
    "        n = len(colors)\n",
    "        graph = defaultdict(set)\n",
    "        for i in range(n):\n",
    "            graph[i] = set()\n",
    "\n",
    "        for edge in edges:\n",
    "            start = edge[0]\n",
    "            end = edge[1]\n",
    "            graph[start].add(end)\n",
    "\n",
    "        n = len(graph)\n",
    "        node_colors = [None] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if node_colors[i] is None:\n",
    "                res = self.dfs(i, graph, color_set, colors, node_colors)\n",
    "                if res is None:\n",
    "                    return -1\n",
    "        max_num = 0\n",
    "        for node_color in node_colors:\n",
    "            for color in node_color:\n",
    "                max_num = max(node_color[color], max_num)\n",
    "        # print(node_colors)\n",
    "        return max_num\n",
    "\n",
    "\n",
    "    def dfs(self, node, graph, color_set, colors, node_colors):\n",
    "        if len(graph[node]) == 0:\n",
    "            color_count = defaultdict(int)\n",
    "            for color in color_set:\n",
    "                if colors[node] == color:\n",
    "                    color_count[color] = 1\n",
    "                else:\n",
    "                    color_count[color] = 0\n",
    "                node_colors[node] = color_count\n",
    "            return color_count\n",
    "        else:\n",
    "            for child in graph[node]:\n",
    "\n",
    "                # print(graph[node], child, node_colors)\n",
    "                if node_colors[child] == 1:\n",
    "                    return None\n",
    "                elif node_colors[child] is not None:\n",
    "                    continue\n",
    "                else:\n",
    "                    node_colors[child] = 1\n",
    "                    res = self.dfs(child, graph, color_set, colors, node_colors)\n",
    "                    if res is None:\n",
    "                        return None\n",
    "                    node_colors[child] = res\n",
    "            color_count = defaultdict(int)\n",
    "            for color in color_set:\n",
    "                max_color_count = 0\n",
    "                for child in graph[node]:\n",
    "                    max_color_count = max(max_color_count, node_colors[child][color])\n",
    "                color_count[color] = max_color_count\n",
    "            color_count[colors[node]] += 1\n",
    "            node_colors[node] = color_count\n",
    "            return color_count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        colors = list(colors)\n",
    "        for i, x in enumerate(colors):\n",
    "            colors[i] = ord(x) - ord('a')\n",
    "\n",
    "        vis  = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "\n",
    "        mark = [0] * n\n",
    "        def is_acyclic(i):\n",
    "            if mark[i] == -1:\n",
    "                return False\n",
    "            if mark[i] == 1:\n",
    "                return True\n",
    "            mark[i] = -1\n",
    "            for nei in g[i]:\n",
    "                if not is_acyclic(nei):\n",
    "                    return False \n",
    "            mark[i] = 1\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if not is_acyclic(i):\n",
    "                return -1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(u): # return best of each color\n",
    "            nonlocal ans\n",
    "            ret = [0] * 30\n",
    "            for nei in g[u]:\n",
    "                sub = dfs(nei)\n",
    "                for c in range(30):\n",
    "                    ret[c] = max(ret[c], sub[c])\n",
    "            ret[colors[u]] += 1\n",
    "            ans = max(ans, max(ret))\n",
    "            # print(u, ret)\n",
    "            return ret\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        edge_dict = defaultdict(list)\n",
    "        for i in edges:\n",
    "            edge_dict[i[0]].append(i[1])\n",
    "        state = [0] * n    # 0 未开始搜索 1 正在搜索 2 结束搜索\n",
    "        result_record = [defaultdict(int) for _ in range(n)] # result_record[i]记录从i开始所有路径的颜色 \n",
    "        result = 0\n",
    "        def dfs(start):\n",
    "            state[start] = 1\n",
    "            for to in edge_dict[start]:\n",
    "                if state[to] == 1:\n",
    "                    return False\n",
    "                elif state[to] == 0 and not dfs(to):\n",
    "                    return False\n",
    "                for i in result_record[to].keys():\n",
    "                    result_record[start][i] = max(result_record[start][i], result_record[to][i])\n",
    "            result_record[start][colors[start]] += 1\n",
    "            state[start] = 2\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if state[i] == 0:\n",
    "                if not dfs(i):\n",
    "                    return -1\n",
    "                maxn = max(result_record[i].values())\n",
    "                result = max(result, maxn)\n",
    "        return result\n",
    "                \n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        dct = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "        n = len(colors)\n",
    "        if not self.canFinish(n, edges):\n",
    "            return -1\n",
    "        dct2 = {}\n",
    "        \n",
    "        def dfs(cur: int, s: str) -> int:\n",
    "            if (cur, s) in dct2:\n",
    "                return dct2[(cur, s)]\n",
    "            res = 0\n",
    "            for i in dct[cur]:\n",
    "                res = max(res, (colors[i] == s)+dfs(i, s))\n",
    "            dct2[(cur, s)] = res\n",
    "            return res\n",
    "            \n",
    "        res = 0\n",
    "        for i in set(colors):\n",
    "            dct2 = {}\n",
    "            for j in range(n):\n",
    "                res = max(res, (i == colors[j])+dfs(j, i))\n",
    "        return res\n",
    "        \n",
    "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    "        dct = defaultdict(list)\n",
    "        for i, j in prerequisites:\n",
    "            dct[i].append(j)\n",
    "        nums = [0]*numCourses\n",
    "\n",
    "        def dfs(num: int) -> bool:\n",
    "            if nums[num] == -1:\n",
    "                return True\n",
    "            if nums[num] == 1:\n",
    "                return False\n",
    "            nums[num] = 1\n",
    "            for i in dct[num]:\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "            nums[num] = -1\n",
    "            return True\n",
    "        \n",
    "        return all(dfs(i) for i in range(numCourses))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for x, y in edges:\n",
    "\n",
    "            g[x].append(y)\n",
    "            deg[y] += 1\n",
    "\n",
    "        q = deque([i for i, v in enumerate(deg) if v == 0])\n",
    "\n",
    "        f = [Counter() for _ in range(n + 1)]\n",
    "        nodes = n\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            c = colors[x]\n",
    "            nodes -= 1\n",
    "            f[x][c] += 1\n",
    "\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                for c in ascii_lowercase:\n",
    "                    f[y][c] = max(f[x][c], f[y][c])\n",
    "                if deg[y] == 0:\n",
    "                    q.append(y)\n",
    "\n",
    "        return max(max(f[i].values()) for i in range(n)) if nodes == 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.r = 0\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        # 只记录每个点的可行路径的颜色最大值\n",
    "        g = {}\n",
    "        n = len(colors)\n",
    "        vis = [-1 for _ in range(n)]\n",
    "        degree = [0 for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            if x == y:\n",
    "                return -1\n",
    "            if x not in g.keys():\n",
    "                g[x] = [y]\n",
    "            else:\n",
    "                g[x].append(y)\n",
    "            degree[y] += 1\n",
    "        paths = {}\n",
    "        res = []\n",
    "\n",
    "        # 找环\n",
    "        def get_round(cur):\n",
    "            mark[cur] = 1\n",
    "            vis[cur] = 1\n",
    "            if cur not in g.keys():\n",
    "                return \n",
    "            for i in g[cur]:\n",
    "                if mark[i] == 1:\n",
    "                    self.r = 1\n",
    "                    break\n",
    "                if vis[i] == -1:\n",
    "                    get_round(i)\n",
    "                    mark[i] = -1\n",
    "            \n",
    "        for i in range(n):\n",
    "            if vis[i] == -1:\n",
    "                mark = [-1] * n\n",
    "                get_round(i)\n",
    "\n",
    "        if self.r == 1:\n",
    "            return -1\n",
    "\n",
    "        def dfs(cur):\n",
    "            if cur in paths.keys():\n",
    "                return paths[cur]\n",
    "            if cur not in g.keys():\n",
    "                paths[cur] = {colors[cur]: 1}\n",
    "                return paths[cur]\n",
    "            paths[cur] = {}\n",
    "            for j in g[cur]:\n",
    "                if j not in paths.keys():\n",
    "                    a = dfs(j)\n",
    "                    for k, v in a.items():\n",
    "                        if k not in paths[cur].keys():\n",
    "                            paths[cur][k] = v\n",
    "                        else:\n",
    "                            paths[cur][k] = max(v, paths[cur][k])\n",
    "                else:\n",
    "                    a = paths[j]\n",
    "                    for k, v in a.items():\n",
    "                        if k not in paths[cur].keys():\n",
    "                            paths[cur][k] = v\n",
    "                        else:\n",
    "                            paths[cur][k] = max(v, paths[cur][k])\n",
    "            paths[cur][colors[cur]] = paths[cur].get(colors[cur], 0) + 1\n",
    "            return paths[cur]\n",
    "\n",
    "        ans = 0\n",
    "        for idx, i in enumerate(degree):\n",
    "            if i == 0:\n",
    "                for k, v in dfs(idx).items():\n",
    "                    ans = max(ans, v)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        num_nodes = len(colors)\n",
    "        graph = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for e in edges:\n",
    "            graph[e[0]].append(e[1])\n",
    "            indegree[e[1]] += 1\n",
    "        \n",
    "        self.visits = set()\n",
    "        self.black = set()\n",
    "        self.node_color = defaultdict(dict)\n",
    "        self.have = False\n",
    "        res = 0\n",
    "        for node in range(num_nodes):\n",
    "            if indegree[node] == 0:\n",
    "                node_dict = self.dfs(graph, node, colors)\n",
    "                if self.have:\n",
    "                    return -1\n",
    "                for c in node_dict:\n",
    "                    res = max(res, node_dict[c])\n",
    "        if len(self.visits)!=num_nodes:\n",
    "            return -1\n",
    "        return res\n",
    "                \n",
    "    def dfs(self, graph, node, colors):\n",
    "        \n",
    "        self.visits.add(node)\n",
    "        curr_color = colors[node]\n",
    "        curr_dict = {}\n",
    "        for child in graph[node]:\n",
    "            if child not in self.visits:\n",
    "                child_dict = self.dfs(graph, child, colors)\n",
    "            elif child in self.black:\n",
    "                child_dict = self.node_color[child]\n",
    "            else:\n",
    "                self.have = True\n",
    "                return self.node_color[child]\n",
    "            for color in child_dict:\n",
    "                if color in curr_dict:\n",
    "                    curr_dict[color] = max(curr_dict[color], child_dict[color])\n",
    "                else:\n",
    "                    curr_dict[color] = child_dict[color]\n",
    "        if curr_color not in curr_dict:\n",
    "            curr_dict[curr_color] = 1\n",
    "        else:\n",
    "            curr_dict[curr_color] += 1\n",
    "        self.node_color[node] = curr_dict\n",
    "        self.black.add(node)\n",
    "        \n",
    "        return curr_dict\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def dfs(node, edges, visited, numbers, order_list):\n",
    "    if visited[node]: return True\n",
    "    visited[node] = True\n",
    "    order_list.append(node)\n",
    "    for neighbour in edges[node]:\n",
    "        numbers[neighbour] -= 1\n",
    "        if numbers[neighbour] == 0:\n",
    "            dfs(neighbour, edges, visited, numbers, order_list)\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        order_list = []\n",
    "        visited = [False for _ in range(len(colors))]\n",
    "        leafs = [True for _ in range(len(colors))]\n",
    "        parents = [[] for _ in range(len(colors))]\n",
    "        neighbours = [[] for _ in range(len(colors))]\n",
    "        for x in edges:\n",
    "            leafs[x[0]] = False\n",
    "            parents[x[1]].append(x[0])\n",
    "            neighbours[x[0]].append(x[1])\n",
    "        numbers = [len(x) for x in neighbours]\n",
    "        for i in range(len(leafs)):\n",
    "            if not leafs[i]: continue\n",
    "            dfs(i, parents, visited, numbers, order_list)\n",
    "        if not all([x == 0 for x in numbers]):\n",
    "            return -1\n",
    "    \n",
    "        largest = [[0 for _ in range(26)] for _ in range(len(colors))]\n",
    "        for i in order_list:\n",
    "            for j in range(26):\n",
    "                for neighbour in neighbours[i]:\n",
    "                    largest[i][j] = max(largest[i][j], largest[neighbour][j]) \n",
    "                if colors[i] == chr(ord('a') + j):\n",
    "                    largest[i][j] += 1\n",
    "        largest = np.max([np.max(x) for x in largest])\n",
    "        return largest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, A: str, edges: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 2060 ms ... 72 % ... 124.6 MB ... 17 %\n",
    "        #  time: O(V+E)\n",
    "        # space: O(V+E)\n",
    "        \n",
    "        def has_cycle_topological(n, edges):               # 检测有向图中是否有环：方法一【依靠剪枝进行拓扑排序】\n",
    "            p2c = collections.defaultdict(set)\n",
    "            c2p = collections.defaultdict(set)\n",
    "            for p,c in edges:\n",
    "                if p == c:\n",
    "                    return True\n",
    "                p2c[p].add(c)\n",
    "                c2p[c].add(p)\n",
    "            leaf = {i for i in range(n) if i not in p2c}   # 从 out_degree=0 的叶子结点开始 upwards 剪枝\n",
    "            while leaf:\n",
    "                newleaf = set()\n",
    "                for c in leaf:\n",
    "                    for p in c2p[c]:\n",
    "                        if len(p2c[p]) == 1:\n",
    "                            newleaf.add(p)\n",
    "                            del p2c[p]\n",
    "                        else:\n",
    "                            p2c[p].remove(c)\n",
    "                    del c2p[c]\n",
    "                leaf = newleaf\n",
    "            return len(c2p) > 0\n",
    "        \n",
    "        def dfs(p):\n",
    "            self.visit[p] = 1                              # 把白色改为灰色，表示开启访问\n",
    "            for c in self.p2c[p]:\n",
    "                if self.visit[c] == 1:                     # DFS 过程中，遇到灰色结点，则说明遇到环\n",
    "                    return True\n",
    "                elif not self.visit[c] and dfs(c):\n",
    "                    return True\n",
    "            self.visit[p] = 2                              # 把灰色改为黑色，表示完成访问\n",
    "            return False\n",
    "        \n",
    "        def has_cycle_coloring(n, edges):                  # 检测有向图是否有环：方法二【DFS + 着色法】\n",
    "            self.p2c = collections.defaultdict(set)\n",
    "            for p,c in edges:\n",
    "                if p == c:\n",
    "                    return True\n",
    "                self.p2c[p].add(c)\n",
    "            self.visit = [0]*n                             # 0：结点未被访问过，1：结点及其后代访问已开始但未结束，2：结点及其后代访问已完全结束\n",
    "            for p in range(n):\n",
    "                if not self.visit[p] and dfs(p):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        seen = {}\n",
    "        def func(i):                                       # res[j] 是从 i 结点向下走可得的 j 颜色最大频次，res[j1] 和 res[j2] 很可能来自不同路径\n",
    "            if i not in seen:\n",
    "                res = [0]*len(loc)\n",
    "                for c in p2c[i]:\n",
    "                    tmp = func(c)\n",
    "                    res = [max(res[j], tmp[j]) for j in range(len(loc))]\n",
    "                res[loc[A[i]]] += 1\n",
    "                seen[i] = res\n",
    "            return seen[i]\n",
    "        \n",
    "        n = len(A)\n",
    "        # if has_cycle_topological(n, edges):\n",
    "        if has_cycle_coloring(n, edges):\n",
    "            return -1\n",
    "        p2c = collections.defaultdict(set)\n",
    "        for p,c in edges:\n",
    "            p2c[p].add(c)\n",
    "        loc = {color:i for i,color in enumerate(sorted(set(A)))}\n",
    "        return max(max(func(i)) for i in range(n))\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        graph = [ [] for _ in range(n)]\n",
    "\n",
    "        indgree = [0]*n\n",
    "        for i,j in edges: \n",
    "            graph[i].append(j)\n",
    "            indgree[j] += 1\n",
    "        \n",
    "        orda = ord('a')\n",
    "        COLORS = [ ord(c) - orda for c in colors]\n",
    "        COLOR_COUNT = [ [0]*26 for _ in range(n)]\n",
    "\n",
    "        # 拓扑排序判断有没有环\n",
    "        N = len(graph)\n",
    "        indegree = [0]*N\n",
    "        for i in range(N):\n",
    "            for j in graph[i]:\n",
    "                indegree[j] += 1\n",
    "        q = deque()\n",
    "        vis = 0\n",
    "        for _ in range(N):\n",
    "            if indegree[_] == 0:\n",
    "                q.append(_)\n",
    "                vis += 1\n",
    "        while q: \n",
    "            node = q.popleft()\n",
    "            for j in graph[node]:\n",
    "                indegree[j] -= 1\n",
    "                if indegree[j] == 0:\n",
    "                    q.append(j)\n",
    "                    vis += 1\n",
    "        if vis < N:return -1\n",
    "\n",
    "        vis = [False]*n\n",
    "        def dfs(x):\n",
    "            COLOR_COUNT[x][ COLORS[x] ] = max(COLOR_COUNT[x][ COLORS[x] ],1)\n",
    "            for y in graph[x]:\n",
    "                indgree[y] -= 1\n",
    "                if not vis[y]:\n",
    "                    vis[y] = True \n",
    "                    dfs(y)\n",
    "                for c in range(26):\n",
    "                    COLOR_COUNT[x][c] = max( COLOR_COUNT[x][c], ( COLORS[x] == c) + COLOR_COUNT[y][c] ) \n",
    "\n",
    "        ans = 1\n",
    "        starts = [i for i in range(n) if indgree[i]==0]\n",
    "        for i in starts: \n",
    "            dfs(i)\n",
    "            ans = max( ans, max(COLOR_COUNT[i])  ) \n",
    "        return ans if sum(indgree) == 0 else -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1857 lang=python3\n",
    "#\n",
    "# [1857] 有向图中最大颜色值\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.ans = 0\n",
    "        self.circle = False\n",
    "\n",
    "\n",
    "    def largestPathValue(self, colors: str, edges) -> int:\n",
    "        adj = [[] for _ in range(len(colors))]\n",
    "        for e in edges:\n",
    "            adj[e[0]].append(e[1])\n",
    "\n",
    "        visit = set()\n",
    "        color_set = set(colors)\n",
    "       \n",
    "        s = set()\n",
    "        dp = [{c:0 for c in color_set} for _ in range(len(colors))]\n",
    "        \n",
    "\n",
    "        def func(i):\n",
    "            if i in s:\n",
    "                self.circle = True\n",
    "                return \n",
    "            \n",
    "            if i in visit:\n",
    "                return\n",
    "            \n",
    "            dp[i][colors[i]] = 1\n",
    "            s.add(i)\n",
    "            for j in adj[i]:\n",
    "                if j not in visit:\n",
    "                    func(j)\n",
    "                    visit.add(j)\n",
    "                if self.circle:\n",
    "                    break\n",
    "                for c in color_set:\n",
    "                    dp[i][c] = max(dp[i][c], dp[j][c] + (1 if c == colors[i] else 0))\n",
    "            s.remove(i)\n",
    "\n",
    "        \n",
    "        for i in range(len(colors)):\n",
    "            func(i)\n",
    "            if self.circle:\n",
    "                return -1\n",
    "        \n",
    "        \n",
    "        return max(max(dp[i].values()) for i in range(len(colors)))\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(colors) # 节点数\n",
    "\n",
    "        # 图表示成邻接链表\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            i, j = edge[0], edge[1]\n",
    "            graph[i].append(j)\n",
    "\n",
    "        #颜色表示成数字（仅限python）\n",
    "        color = []\n",
    "        for i in range(n):\n",
    "            color.append(ord(colors[i]) - ord('a'))\n",
    "\n",
    "        #下面就是一个简单的记忆化深度搜索，步骤和拓扑排序类似\n",
    "\n",
    "        f = [[0] * 26 for _ in range(n)] # <每个节点每种颜色的最大值 \\U0001f495>\n",
    "        searched = [0] * n # 可以用 max(f[i]) == 0 代替\n",
    "        marked = [0] * n # 标记路径找环\n",
    "        has_cycle = False\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal has_cycle\n",
    "            if not graph[i]:\n",
    "                f[i][color[i]] = 1\n",
    "                return \n",
    "            marked[i] = 1\n",
    "            searched[i] = 1\n",
    "            for adj in graph[i]:\n",
    "                if marked[adj]: \n",
    "                    has_cycle = True\n",
    "                    break\n",
    "                if not searched[adj]:\n",
    "                    dfs(adj)\n",
    "                    marked[adj] = 0\n",
    "                for j in range(26):\n",
    "                    f[i][j] = max(f[i][j], f[adj][j])\n",
    "            f[i][color[i]] += 1\n",
    "        \n",
    "        for i in range(len(colors)):\n",
    "            if not searched[i]:\n",
    "                marked = [0] * n\n",
    "                dfs(i)\n",
    "                if has_cycle: return -1\n",
    "        \n",
    "        return max(max(f[i]) for i in range(n))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, c: str, e: List[List[int]]) -> int:\n",
    "        e = set([(i, j) for i, j in e])\n",
    "        n = len(c)\n",
    "        g = [[] for j in range(n)]\n",
    "        ind = [0]*n\n",
    "        for x, y in e:\n",
    "            if x==y:return -1 \n",
    "            g[x].append(y)\n",
    "            ind[y] += 1 \n",
    "        use = set(c)\n",
    "        v = defaultdict(int)\n",
    "        s = [j for j in range(n) if ind[j]==0]\n",
    "        def dfs(x):\n",
    "            t = c[x]\n",
    "            v[(x, t)] += 1\n",
    "            for y in g[x]:\n",
    "                for j in use:\n",
    "                    if v[(x, j)]>v[(y, j)]:\n",
    "                        v[(y, j)] = v[(x, j)]\n",
    "                ind[y] -= 1 \n",
    "                if ind[y]==0:\n",
    "                    dfs(y) \n",
    "        # print(ind)\n",
    "        for j in s:\n",
    "            dfs(j)\n",
    "        s = {j[0] for j in v}\n",
    "\n",
    "        if len(s)==n:\n",
    "            return max(v.values())\n",
    "\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        colors = [ord(x) - ord('a') for x in colors]\n",
    "        deg = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            deg[b] += 1\n",
    "        \n",
    "        q = [i for i in range(n) if deg[i] == 0]\n",
    "        start = q.copy()\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                for son in g[node]:\n",
    "                    deg[son] -= 1\n",
    "                    if deg[son] == 0:\n",
    "                        q.append(son)\n",
    "        if any(deg[i] for i in range(n)):\n",
    "            return -1\n",
    "        \n",
    "        def dfs(node):\n",
    "            counter = [0] * 26\n",
    "            for son in g[node]:\n",
    "                soncnt = cnt.get(son)\n",
    "                if not soncnt:\n",
    "                    cnt[son] = soncnt = dfs(son)\n",
    "                for i in range(26):\n",
    "                    if counter[i] < soncnt[i]:\n",
    "                        counter[i] = soncnt[i]   \n",
    "            counter[colors[node]] += 1\n",
    "            return counter\n",
    "\n",
    "            \n",
    "        cnt = dict()\n",
    "        ret = 0\n",
    "        for node in start:\n",
    "            cnt[node] = dfs(node)\n",
    "            ret = max(ret, max(cnt[node]))\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, c: str, e: List[List[int]]) -> int:\n",
    "        e = set([(i, j) for i, j in e])\n",
    "        n = len(c)\n",
    "        g = [[] for j in range(n)]\n",
    "        ind = defaultdict(int)\n",
    "        for x, y in e:\n",
    "            if x==y:return -1 \n",
    "            g[x].append(y)\n",
    "            ind[y] += 1 \n",
    "        use = set(c)\n",
    "        v = defaultdict(int)\n",
    "        s = [j for j in range(n) if ind[j]==0]\n",
    "        def dfs(x):\n",
    "            t = c[x]\n",
    "            v[(x, t)] += 1\n",
    "            for y in g[x]:\n",
    "                for j in use:\n",
    "                    v[(y, j)] = max(v[(x, j)], v[(y, j)]) \n",
    "                ind[y] -= 1 \n",
    "                if ind[y]==0:\n",
    "                    dfs(y) \n",
    "        # print(ind)\n",
    "        for j in s:\n",
    "            dfs(j)\n",
    "        s = set([j[0] for j in v])\n",
    "\n",
    "        if len(s)==n:\n",
    "            return max(v.values())\n",
    "\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        def dfs(node:int,depth:int)->bool:\n",
    "            if depth > N: # circle detected\n",
    "                return False\n",
    "            if nodes[node][-1] == 1: #already searched\n",
    "                return True\n",
    "            for child in graph[node]:\n",
    "                if not dfs(child,depth+1):\n",
    "                    return False\n",
    "            for i in range(C):\n",
    "                nodes[node][i] = max([nodes[child][i] for child in graph[node]],default=0)\n",
    "            nodes[node][plate[colors[node]]] += 1\n",
    "            nodes[node][-1] = 1\n",
    "            return True\n",
    "\n",
    "        plate = {c:i for i,c in enumerate(list(set(colors)))}\n",
    "        C = len(plate)\n",
    "        N = len(colors)\n",
    "        nodes = [[0]*(C+1) for _ in colors]\n",
    "        result = 0\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "        for i in range(len(colors)):\n",
    "            if not dfs(i,1):\n",
    "                return -1\n",
    "            result = max(result,max(nodes[i][:C]))\n",
    "        return result\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        degrees = [0] * n\n",
    "        for u, v in edges:\n",
    "            if u != v:\n",
    "                graph[u].append(v)\n",
    "                degrees[v] += 1\n",
    "            else:\n",
    "                return -1\n",
    "        status = [0] * n\n",
    "        colorSet = set(list(colors))\n",
    "        table = {}\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if self.checkCycle(graph, i, status):\n",
    "                return -1\n",
    "        for i in range(n):\n",
    "            if degrees[i] == 0:\n",
    "                for color in colorSet:\n",
    "                    res = max(res, self.searchVal(graph, i, color, colors, table))\n",
    "        return res\n",
    "\n",
    "    def checkCycle(self, graph, node, status):\n",
    "        status[node] = 1\n",
    "        for anode in graph[node]:\n",
    "            if status[anode] == 1:\n",
    "                return True\n",
    "            elif status[anode] == 0:\n",
    "                if self.checkCycle(graph, anode, status):\n",
    "                    return True\n",
    "        status[node] = 2\n",
    "        return False\n",
    "\n",
    "    def searchVal(self, graph, node, color, colors, table):\n",
    "        if (node, color) not in table:\n",
    "            if len(graph[node]) == 0:\n",
    "                if colors[node] == color:\n",
    "                    table[(node, color)] = 1\n",
    "                else:\n",
    "                    table[(node, color)] = 0\n",
    "            else:\n",
    "                res = 0\n",
    "                for anode in graph[node]:\n",
    "                    if colors[node] == color:\n",
    "                        res = max(res, self.searchVal(graph, anode, color, colors, table) + 1)\n",
    "                    else:\n",
    "                        res = max(res, self.searchVal(graph, anode, color, colors, table))\n",
    "                table[(node, color)] = res\n",
    "        return table[(node, color)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        adj = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "\n",
    "        # return the max freq of color starts from node\n",
    "        def dfs(node: int) -> int:\n",
    "            if node in path:\n",
    "                return float('inf')\n",
    "\n",
    "            if node in visit:\n",
    "                return 0\n",
    "            \n",
    "            visit.add(node)\n",
    "            path.add(node)\n",
    "\n",
    "            current_color = ord(colors[node]) - ord('a')\n",
    "            memo[node][current_color] = 1\n",
    "            # go to neighbors\n",
    "            for v in adj[node]:\n",
    "                if dfs(v) == float('inf'):\n",
    "                    return float('inf')\n",
    "                # check each color\n",
    "                for c in range(26):\n",
    "                    memo[node][c] = max(\n",
    "                        memo[node][c],\n",
    "                        (1 if c == current_color else 0) + memo[v][c]\n",
    "                    )\n",
    "            \n",
    "            path.remove(node)\n",
    "            return max(memo[node])\n",
    "            \n",
    "        n = len(colors)\n",
    "        res = 0\n",
    "        visit = set()\n",
    "        path = set()\n",
    "        # memo[node][color] = max freq color starts from mnode\n",
    "        memo = [[0] * 26 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            res = max(res, dfs(i))\n",
    "\n",
    "        return -1 if res == float('inf') else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import Counter, List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        temp = defaultdict(list)\n",
    "        for u, v in edges : temp[u].append(v)\n",
    "        edges = temp\n",
    "\n",
    "        n = len(colors)\n",
    "        mc = [Counter() for _ in range(n)]\n",
    "        visited = [0] * n\n",
    "        def search(i) :\n",
    "            if visited[i] : return visited[i] == 1\n",
    "\n",
    "            visited[i] = 1\n",
    "            for j in edges[i] :\n",
    "                if search(j) : return True\n",
    "                for k,v in mc[j].items() : mc[i][k] = max(mc[i][k], v)\n",
    "            mc[i][colors[i]] += 1\n",
    "            visited[i] = 2\n",
    "\n",
    "            return False\n",
    "\n",
    "        res = -1\n",
    "        for i in range(n) :\n",
    "            if search(i) : return -1\n",
    "            res = max(res, max(mc[i].values()))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        road = defaultdict(list)\n",
    "        \n",
    "        nodes = set()\n",
    "        for x,y in edges:\n",
    "            road[x].append(y)\n",
    "            nodes\n",
    "        \n",
    "         \n",
    "        status = {}        \n",
    "        que = deque()\n",
    "        def dfs(node):            \n",
    "            status[node] = 1\n",
    "            for next in road[node]:\n",
    "                if next not in status:                   \n",
    "                    if not dfs(next):\n",
    "                        return False\n",
    "                    \n",
    "                # 有环\n",
    "                if status[next] == 1:\n",
    "                    return False\n",
    "            status[node] = 2\n",
    "            que.appendleft(node)\n",
    "            return True\n",
    "        \n",
    "        n = len(colors)       \n",
    "        for i in range(n):\n",
    "            if i not in status:\n",
    "                if not dfs(i):\n",
    "                    return -1\n",
    "        \n",
    "        \n",
    "        check_list = []\n",
    "        for i in range(26):\n",
    "            check_list.append(chr(i+97))\n",
    "        #print(check_list)\n",
    "                \n",
    "        def getMaxCounter(a,b):\n",
    "            res = Counter()\n",
    "            for w in check_list:\n",
    "                res[w] = max(a[w],b[w])\n",
    "            return res\n",
    "            \n",
    "        # 每个节点的每个字母的最大计数\n",
    "        dp = defaultdict(Counter)\n",
    "                              \n",
    "        res = 1\n",
    "        #print(que)\n",
    "        while que:\n",
    "            node = que.pop()           \n",
    "            color = colors[node] \n",
    "                       \n",
    "            last = Counter()\n",
    "            for next in road[node]:                \n",
    "                last = getMaxCounter(last,dp[next])\n",
    "            last[color] += 1\n",
    "            dp[node] = last\n",
    "            res = max(res,last.most_common(1)[0][1])\n",
    "        \n",
    "       \n",
    "        \n",
    "                \n",
    "                      \n",
    "            \n",
    "        #print(dp)\n",
    "        return res\n",
    "        \n",
    "                    \n",
    "                    \n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    m = 0\n",
    "    p = 0\n",
    "    def build_graph(self,colors, edges):\n",
    "        graph = [[] for i in range(len(colors))]\n",
    "        inp = [0]*len(colors)\n",
    "        for i,j in edges:\n",
    "            graph[i].append(j)\n",
    "            inp[j] += 1 \n",
    "        return graph, inp\n",
    "    def dfs(self, graph, colors, v, k,  path):\n",
    "        rin = [0]*26\n",
    "        if graph[k] == [] or self.p == 1:\n",
    "            rin[ord(colors[k])- ord('a')] += 1\n",
    "            return rin\n",
    "        if path[k]:\n",
    "            self.p = 1\n",
    "            return rin\n",
    "        if sum(v[k]) != 0:\n",
    "            return v[k].copy()\n",
    "        path[k] = True\n",
    "        for i in graph[k]:\n",
    "            tmp = self.dfs(graph, colors, v, i,  path)\n",
    "            tmp[ord(colors[k])- ord('a')] += 1\n",
    "            for j in range(26):\n",
    "                rin[j] = max(tmp[j], rin[j])\n",
    "        path[k] = False\n",
    "        v[k] = rin[:]\n",
    "        return rin\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        graph, inp = self.build_graph(colors, edges)\n",
    "        print(graph)\n",
    "        #print(graph,inp)\n",
    "        v = [[0]*26 for i in range(len(colors))]\n",
    "        for i,j in enumerate(inp):\n",
    "            #print(v)\n",
    "            if sum(v[i])!=0:\n",
    "                continue\n",
    "            path = [False]*len(colors)\n",
    "            rin = self.dfs(graph, colors, v, i,  path)\n",
    "            if max(rin) > self.m:\n",
    "                self.m = max(rin)\n",
    "        if self.p == 1 or 0 not in inp:\n",
    "            return -1\n",
    "        else:\n",
    "            return self.m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "       \n",
    "        self.circle = False\n",
    "\n",
    "\n",
    "    def largestPathValue(self, colors: str, edges) -> int:\n",
    "\n",
    "        adj = [[] for _ in range(len(colors))]\n",
    "        for e in edges:\n",
    "            adj[e[0]].append(e[1])\n",
    "\n",
    "        color_set = set(colors)\n",
    "       \n",
    "        s = set()\n",
    "        dp = [{c:0 for c in color_set} for _ in range(len(colors))]\n",
    "        \n",
    "        @cache\n",
    "        def func(i):\n",
    "            if i in s:\n",
    "                self.circle = True\n",
    "                return \n",
    "            \n",
    "            \n",
    "             \n",
    "            \n",
    "            dp[i][colors[i]] = 1\n",
    "            s.add(i)\n",
    "            for j in adj[i]:\n",
    "                func(j)\n",
    "                if self.circle:\n",
    "                    break\n",
    "                for c in color_set:\n",
    "                    dp[i][c] = max(dp[i][c], dp[j][c] + (1 if c == colors[i] else 0))\n",
    "            s.remove(i)\n",
    "\n",
    "        \n",
    "        for i in range(len(colors)):\n",
    "            func(i)\n",
    "            if self.circle:\n",
    "                return -1\n",
    "        \n",
    "        \n",
    "        return max(max(dp[i].values()) for i in range(len(colors)))\n",
    "    \n",
    "# print(Solution().largestPathValue(colors = \"a\", edges = [[0,0]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        g = defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            g[u].add(v)\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node, target):\n",
    "            ans = [0,1][colors[node] == target]\n",
    "            color[node] = 1\n",
    "            res = 0\n",
    "            for nei in g[node]:\n",
    "                if color[nei] == 1:\n",
    "                    return False,0\n",
    "                elif color[nei] == 0:\n",
    "                    flag, tmp = dfs(nei, target)\n",
    "                    if not flag:\n",
    "                        return False, 0\n",
    "                    if tmp > res:\n",
    "                        res = tmp\n",
    "            color[node] = 0\n",
    "            return True, ans + res\n",
    "        ans = 0\n",
    "        color = [0]*n\n",
    "        for l in set([c for c in colors]):\n",
    "            for node in range(n):\n",
    "                if color[node] == 0:\n",
    "                    flag, res = dfs(node, l)\n",
    "                    if not flag:\n",
    "                        return -1\n",
    "                    if res > ans:\n",
    "                        ans = res\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        #copy \n",
    "        n = len(colors)\n",
    "        g = defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            g[u].add(v)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node,target):\n",
    "            ans = [0,1][colors[node]== target]\n",
    "            color[node] =1\n",
    "            res = 0\n",
    "            for nei in g[node]:\n",
    "                if color[nei] ==1:\n",
    "                    return False,0\n",
    "                elif color[nei] == 0:\n",
    "                    flag,tmp = dfs(nei,target)\n",
    "                    if not flag:\n",
    "                        return False,0\n",
    "                    if tmp >res:\n",
    "                        res = tmp\n",
    "            color[node] = 0\n",
    "            return True,ans + res\n",
    "        ans = 0\n",
    "        for l in set([c for c in colors]):\n",
    "            color = [0] * n\n",
    "            for node in range(n):\n",
    "                flag,res = dfs(node,l)\n",
    "                if not flag:\n",
    "                    return -1\n",
    "                if res >ans:\n",
    "                    ans = res\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from functools import cache\n",
    "from typing import List\n",
    "inf = float('inf')\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        nt = defaultdict(set)\n",
    "        queue = set()\n",
    "        pre = {}\n",
    "        for i in range(n):\n",
    "            pre[i] = set()\n",
    "            queue.add(i)\n",
    "\n",
    "        for c, t in edges:\n",
    "            nt[c].add(t)\n",
    "            pre[t].add(c)\n",
    "            if t in queue:\n",
    "                queue.remove(t)\n",
    "\n",
    "        nlist = set(queue)\n",
    "        while queue:\n",
    "            qnt = set()\n",
    "            for k in queue:\n",
    "                del pre[k]\n",
    "                for nk in nt[k]:\n",
    "                    if k in pre[nk]:\n",
    "                        pre[nk].remove(k)\n",
    "                    if not len(pre[nk]):\n",
    "                        qnt.add(nk)\n",
    "            queue = qnt \n",
    "\n",
    "        if len(pre.keys()) != 0: return -1\n",
    "\n",
    "        @cache\n",
    "        def dp(i, st):\n",
    "            r = 0\n",
    "            for n in nt[i]:\n",
    "                r = max(r, dp(n, st))\n",
    "            return r + (1 if colors[i] == st else 0)\n",
    "        s_color = set(colors)\n",
    "        res = 0\n",
    "        for i in nlist:\n",
    "            for j in s_color:\n",
    "                res = max(res, dp(i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        adj = [[] for _ in range(n)]\n",
    "        ins = [0] * n\n",
    "        for x, y in edges:\n",
    "            adj[x].append(y)\n",
    "            ins[y] += 1\n",
    "        ins0 = ins[:]\n",
    "        q = deque([x for x, d in enumerate(ins0) if not d])\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            cnt += 1\n",
    "            for y in adj[x]:\n",
    "                ins[y] -= 1\n",
    "                if not ins[y]:\n",
    "                    q.append(y)\n",
    "        if cnt != n: return -1\n",
    "        @lru_cache(None)\n",
    "        def dfs(x): # x为起点各路径的 各颜色最大值\n",
    "            # 子问题个颜色最大值 再取最大\n",
    "            mx = [0] * 26\n",
    "            for y in adj[x]:\n",
    "                sub = dfs(y)\n",
    "                for i in range(26):\n",
    "                    mx[i] = max(mx[i], sub[i])\n",
    "            mx[ord(colors[x]) - ord('a')] += 1\n",
    "            return mx\n",
    "        ans = 0\n",
    "        for x in range(n):\n",
    "            if not ins0[x]:\n",
    "                ans = max(ans, max(dfs(x)))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(i, visited):\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "\n",
    "            cnter = collections.Counter()\n",
    "            for nei in outs[i]:\n",
    "                if visited[nei]: raise\n",
    "                visited[nei] = True\n",
    "                ALL[nei] = True\n",
    "                cnter_nei = dfs(nei, visited)\n",
    "                for clr in cnter_nei.keys():\n",
    "                    cnter[clr] = max(cnter[clr], cnter_nei[clr])\n",
    "                visited[nei] = False\n",
    "            cnter[colors[i]] += 1\n",
    "            cache[i] = cnter\n",
    "            return cnter\n",
    "                \n",
    "        ins = collections.defaultdict(set)\n",
    "        outs = collections.defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            ins[b].add(a)\n",
    "            outs[a].add(b)\n",
    "\n",
    "        N = len(colors)\n",
    "        ALL = [False]*N\n",
    "        starts = [i for i in range(N) if not ins[i]]\n",
    "        if not starts:\n",
    "            return -1\n",
    "\n",
    "        colors += \"#\"\n",
    "        outs[-1] = set(starts)\n",
    "        \n",
    "        try:\n",
    "            cnters = dfs(-1, [False]*N)\n",
    "            if all(ALL):\n",
    "                return max(cnters.values())\n",
    "            else:\n",
    "                return -1\n",
    "        except:\n",
    "            return -1\n",
    "        \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        n = len(colors)\n",
    "        adj = [[] for _ in range(n)]\n",
    "        deg = [0] * n\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            deg[v] += 1\n",
    "        q = collections.deque()      \n",
    "        tmp = deg[::]\n",
    "        nodes = 0\n",
    "        for i in range(n):     \n",
    "            if deg[i] == 0:\n",
    "                q.append(i)\n",
    "                nodes += 1\n",
    "        while q:          \n",
    "            u = q.popleft()\n",
    "            for v in adj[u]:\n",
    "                deg[v] -= 1\n",
    "                if deg[v] == 0:\n",
    "                    q.append(v)\n",
    "                    nodes += 1\n",
    "        if nodes != n:                \n",
    "            return -1\n",
    "        deg = tmp  \n",
    "        @lru_cache(None)\n",
    "        def dfs(u: int) -> List[int]:\n",
    "            freq = [0] * 26\n",
    "            for v in adj[u]:\n",
    "                sub_freq = dfs(v)\n",
    "                for i in range(26):\n",
    "                    freq[i] = max(freq[i], sub_freq[i])\n",
    "            freq[ord(colors[u]) - ord('a')] += 1\n",
    "            return freq \n",
    "        ans = 0   \n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                ans = max(ans, max(dfs(i)))\n",
    "        return ans           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.ans = 0\r\n",
    "        self.circle = False\r\n",
    "\r\n",
    "\r\n",
    "    def largestPathValue(self, colors: str, edges) -> int:\r\n",
    "      \r\n",
    "        adj = {i:[] for i in range(len(colors))}\r\n",
    "        indgree = {i:0 for i in range(len(colors))}\r\n",
    "        for e in edges:\r\n",
    "            adj[e[0]].append(e[1])\r\n",
    "            indgree[e[1]] += 1\r\n",
    "\r\n",
    "        color_set = set(colors)\r\n",
    "       \r\n",
    "        s = set()\r\n",
    "        dp = [{c:0 for c in color_set} for _ in range(len(colors))]\r\n",
    "        \r\n",
    "        @cache\r\n",
    "        def func(i):\r\n",
    "            if i in s:\r\n",
    "                self.circle = True\r\n",
    "                return \r\n",
    "            \r\n",
    "            dp[i][colors[i]] = 1\r\n",
    "            s.add(i)\r\n",
    "            for j in adj[i]:\r\n",
    "                func(j)\r\n",
    "                if self.circle:\r\n",
    "                    break\r\n",
    "                for c in color_set:\r\n",
    "                    dp[i][c] = max(dp[i][c], dp[j][c] + (1 if c == colors[i] else 0))\r\n",
    "            s.remove(i)\r\n",
    "\r\n",
    "        \r\n",
    "        for i in range(len(colors)):\r\n",
    "            func(i)\r\n",
    "            if self.circle:\r\n",
    "                return -1\r\n",
    "                \r\n",
    "        t = 0\r\n",
    "        for k, v in indgree.items():\r\n",
    "            if not v:\r\n",
    "                t = max(t, *(dp[k].values()))\r\n",
    "        \r\n",
    "        return t\r\n",
    "    \r\n",
    "print(Solution().largestPathValue(colors = \"a\", edges = [[0,0]]))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:\n",
    "        m = len(edges)\n",
    "        dct = defaultdict(list)\n",
    "        degree = defaultdict(int)\n",
    "        n = len(colors)\n",
    "        for i, j in edges:\n",
    "            degree[j] += 1\n",
    "            dct[i].append(j)\n",
    "\n",
    "        cnt = 0\n",
    "        in_degree = degree.copy()\n",
    "        stack = [i for i in range(n) if not in_degree[i]]\n",
    "        while stack:\n",
    "            cnt += len(stack)\n",
    "            nex = []\n",
    "            for i in stack:\n",
    "                for j in dct[i]:\n",
    "                    in_degree[j] -= 1\n",
    "                    if not in_degree[j]:\n",
    "                        nex.append(j)\n",
    "            stack = nex\n",
    "        if cnt < n:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(node):\n",
    "            res = [0]*26\n",
    "            for k in dct[node]:\n",
    "                son = dfs(k)\n",
    "                for x in range(26):\n",
    "                    res[x] = res[x] if res[x] > son[x] else son[x]\n",
    "            res[ord(colors[node])-ord('a')] += 1\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if not degree[i]:\n",
    "                cur = max(dfs(i))\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
